题目描述

敌人建造了时空传送仪，他们会用它来对你的基地进行攻击。具体说，你的基地是一个 $n \times n$ 的矩形，敌人将用 $l$ 时间进行进攻，在且仅在时间 $i$，会有茫茫多的敌人出现在点 $(x_i, y_i)$。

你可以建造炮塔来防御敌人的进攻，炮塔能攻击到与之曼哈顿距离不超过 $r$ 的敌人，但是每隔 $k$ 时间才能攻击一次，即若时间 $i$ 进行了攻击，那么时间 $i + k$ 才能进行下一次攻击。

与大多数游戏类似，当炮塔射程内没有敌人时，它会立刻充能完毕，在下一次敌人出现时可以立刻进行攻击。

现在你需要求出，在每个位置放置炮塔分别能消灭最多多少敌人。

输入格式

第一行四个正整数 $n, l, r, k$。
接下来 $l$ 行每行两个正整数，依次表示每个时间敌人的位置。

输出格式

输出一个 $n \times n$ 的矩阵表示每个点的答案。

样例

输入

2 2 1 1
1 1
2 2

输出

1 2
2 1

数据范围与提示

$n \leq 2000, m \leq 20000$