← 返回题目列表

Codeforces · 492/E

E. 万尼亚和菲尔德

中文机器翻译题面 查看原题

Vanya 决定走进 n × n 单元格领域。该字段包含 m 个苹果树,第 i 个苹果树位于坐标为 (xi, yi) 的单元格处。 Vanya 向矢量 (dx, dy) 移动。这意味着,如果 Vanya 现在位于单元格 (x, y),那么下一秒他将位于单元格 $$( ( x + d x ) \bmod n, ( y + d y ) \bmod n )$$。该向量满足以下条件:$$\gcd(n,dx)=\gcd(n,dy)=1$$,其中$$\gcd(a,b)$$是整除a和b的最大整数。当瓦尼亚到达他已经去过的广场时,他结束了他的旅程。

Vanya 想知道他应该从田野的哪个方格开始走,才能看到尽可能多的苹果树。

输入

第一行包含整数 n, m, dx, dy(1 ≤ n ≤ 106, 1 ≤ m ≤ 105, 1 ≤ dx, dy ≤ n) — 田地的大小、苹果树的数量和 Vanya 运动的向量。接下来的 m 行包含整数 xi, yi (0 ≤ xi, yi ≤ n - 1) — 苹果的坐标。一个单元格可能包含多棵苹果树。

输出

打印两个以空格分隔的数字 - 您应该从其开始路径的单元格的坐标。如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

5 5 2 3
0 0
1 2
1 3
2 4
3 1

输出 #1

1 3

输入 #2

2 3 1 1
0 0
0 1
1 1

输出 #2

0 0

注意

在第一个示例中,Vanya 的路径将如下所示: (1, 3) - (3, 1) - (0, 4) - (2, 2) - (4, 0) - (1, 3)

在第二个示例中:(0, 0) - (1, 1) - (0, 0)