当前没有测试数据。

题目描述

小 C 每到午饭时间，总是第一个冲向食堂。

食堂有一排 n 个窗口，第 i 号窗口有一个坐标 $x_i$， 不一定满足坐标递增 。

小 C 爱食堂，小朋友们也爱食堂。

食堂里总共有 m 位小朋友，第 i 位小朋友的坐标为 $y_i$， 不一定满足坐标递增 。由于避免拥挤，所以有 m≤n，即每位小朋友至少能找到一个窗口自己独享。

总而言之，可以将食堂看成一个数轴，窗口和小朋友看成若干个坐标点。

在小朋友的世界中，他们遵循着一套规则：从 0 时刻开始，每过 1 秒钟，每位小朋友朝向 最近的、还没有小朋友停留的 窗口移动 1的距离，如果到两个窗口的距离相等，选择 编号 最小的窗口；当一个窗口有小朋友的时候，在该处 编号 最小的小朋友将在此窗口 停留 ；当小朋友 停留 后，就不会再移动了。

现在小 C 掌握了这套规则，他想知道每位小朋友停留的时刻以及停留的窗口，这样小 C 就能赶在小朋友到达某个窗口前抢到饭。

保证窗口两两坐标不同，不保证小朋友两两坐标不同，不保证初始时小朋友与窗口坐标不同。

输入格式

从文件 canteen.in 中读取数据。

共三行，第一行两个正整数 n 和 m，表示窗口数和小朋友个数；

第二行共 n 个整数，第 i 个数为 $x_i$，描述了窗口的坐标；

第三行共 m 个整数，第 i 个数为 $y_i$，描述了小朋友的坐标。

窗口和小朋友的坐标不一定满足递增。

输出格式

输出到文件 canteen.out 中。

共 m 行，每行两个整数，第 i 行的描述编号为 i 的小朋友，依次表示小朋友停留的时刻、停留的窗口的编号。

样例

4 3
3 -3 9 -11
2 2 0

1 1
15 3
5 2

解释#1

0 时刻时，食堂情况如图：

不难看出 1、2、3 号小朋友的目标为 1 号窗口。

1 时刻时，食堂情况如图：

根据规则，1 号小朋友将在 1 号窗口停留，2 号和 3 号小朋友重新选择 2 号窗口为目标（2 号小朋友虽然跟 3 号距离同时最短，但优先选择编号小的窗口）。

5 时刻时，食堂情况如图：

此时 3 号小朋友将在 2 号窗口停留，2 号小朋友将重新选择 3 号窗口为目标。

15时刻时，食堂情况如图：

2 号小朋友最终在 3 号窗口停留。

6 6
2 -1 0 3 5 -6
1 1 -1 -1 3 4

1 1
9 6
0 2
1 3
0 4
1 5

样例#3

见选手目录下的 canteen/canteen3.in 和 canteen/canteen3.ans。

该组数据满足 $n≤10^2、∣x_i∣,∣y_i​∣≤10^4$。

数据范围

• 对于 $20\%$ 的测试数据满足：$1≤n≤10$，$∣x_i∣,∣y_i​∣≤10^2$。
• 对于 $60\%$ 的测试数据满足：$1≤n≤10^2$，$∣x_i∣,∣y_i​∣≤10^4$
• 对于 $100\%$ 的测试数据满足：$1≤n≤10^3$，$∣x_i∣,∣y_i​∣≤10^9$。
• 对于所有数据：$1≤m≤n，∣x_i∣,∣y_i​∣≤10^9$