#arc145e. [arc145_e]Adjacent XOR

[arc145_e]Adjacent XOR

题目描述

给定两个长度为NN的非负整数序列:A=(A1,A2,,AN)A=(A_1,A_2,\ldots,A_{N})B=(B1,B2,,BN)B=(B_1,B_2,\ldots,B_{N})

判断是否可以通过最多进行 7000070000 次以下操作将AA变为BB。如果可以,请给出一种特定的操作序列。

  • 选择一个整数 KK (1KN)(1\le K \le N)。对于每个整数 i (2iK)i\ (2\leq i \leq K),同时用Ai1AiA_{i-1} \oplus A_i替换 AiA_i 的值。

这里,oplus\\oplus表示按位异或。

什么是按位异或?

非负整数AABB的按位异或,ABA\oplus B,定义如下:

  • 当用二进制表示ABA\oplus B时,2k2^k位置上的数字(k0k \geq 0)为11,当且仅当AABB在该位置的数字恰好有一个为11,否则为00

例如,35=63\oplus 5 = 6 (二进制表示:011101=110011\oplus 101 = 110)。

约束条件

  • 2N10002 \leq N \leq 1000
  • 0Ai,Bi<2600 \leq A_i, B_i < 2^{60}
  • 输入中的所有值都为整数。

输入

输入以以下格式从标准输入给出:

NN A1A_1 A2A_2 \ldots ANA_N B1B_1 B2B_2 \ldots BNB_N

输出

如果无法在最多7000070000次操作中使AA等于BB,则打印“No”。如果可以,请以以下格式打印实现这一目标的操作序列,其中MM是操作次数,KiK_i是第ii次操作选择的整数:

Yes MM K1K_1 K2K_2 \ldots KMK_M

如果存在多个解,则可以接受任意解。

示例输入1

3
1 2 0
1 2 3

示例输出1

Yes
2
2 3

在此输出中,序列AA的变化如下:

  • 初始状态:A=(1,2,0)A=(1, 2, 0)
  • 第一次操作后:A=(1,3,0)A=(1, 3, 0)
  • 第二次操作后:A=(1,2,3)A=(1, 2, 3)

经过两次操作,AABB变得相等,达到了目标。

示例输入2

2
10 100
1 0

示例输出2

No

示例输入3

2
1152921504606846975 0
1152921504606846975 0

示例输出3

Yes
0