题目描述

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

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

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

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

输入格式

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

输出格式

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

样例

input

2 2 1 1
1 1
2 2

output

1 2
2 1

数据范围与提示

$ n \leq 2000, m \leq 20000 $