← 返回题目列表

Codeforces · 161/A

A. 给他们穿上背心!

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

二维王国正在经历艰难时期……今天早上,三维王国向二维王国宣战。这场(可能是武装的)冲突将决定这条直线的最终所有者。

二次元王国有一支n人的正规军。每个士兵都进行了登记,并指出了所需的防弹背心尺寸:第 i 个士兵指出了尺寸 ai。众所周知,士兵们是朴实无华的,因此指挥人员假设士兵们穿着尺寸从 ai - x 到 ai + y(含)的任何背心(指定数字 x、y ≥ 0)都很舒服。

二维王国有 m 件背心可供使用,第 j 件背心的大小等于 bj。帮助动员二维王国的军队:为尽可能多的士兵配备背心。每件背心只能使用一次。如果 ai - x ≤ bj ≤ ai + y,则第 i 个士兵可以穿上第 j 个背心。

输入

第一输入行包含四个整数 n、m、x 和 y (1 ≤ n, m ≤ 105, 0 ≤ x, y ≤ 109) — 士兵数量、背心数量和两个相应的表示士兵朴实无华的数字。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109),按非递减顺序排列,用单个空格分隔 - 所需的背心尺寸。

第三行包含 m 个整数 b1, b2, ..., bm (1 ≤ bj ≤ 109),按非降序排列,用单个空格分隔 - 可用背心的尺寸。

输出

在第一行打印一个整数k——装备防弹背心的士兵的最大数量。

在接下来的 k 行中打印 k 对,每行一对,如“ui vi”(不带引号)。 Pair(ui,vi)表示ui号士兵必须穿vi号背心。士兵和背心按照输入中指定的顺序从 1 开始编号。成对中的所有士兵数量应该成对不同,成对中的所有背心数量也应该成对不同。您可以按任意顺序打印这些对。

如果有多个最佳答案,您可以打印其中任何一个。

示例

输入 #1

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

输出 #1

2
1 1
3 2

输入 #2

3 3 2 2
1 5 9
3 5 7

输出 #2

3
1 1
2 2
3 3

注意

在第一个示例中,您需要背心的尺寸完美匹配:第一个士兵获得第一个背心(尺寸 1),第三个士兵获得第二个背心(尺寸 3)。该示例允许另一个答案,它将第二件背心给第四个士兵而不是第三个。

在第二个示例中,背心尺寸与所需尺寸最多相差 2 个尺寸,因此所有士兵都可以装备。