#P14677. [2023 Regional]BitStack

    ID: 13893 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2100提高逆向思考支配关系有限候选集缩减

[2023 Regional]BitStack

题目描述

Gubcif 正在参加大学入学考试。考试使用一种名为 stacklang 的语言。

现在有一个栈,初始时共有 NN 个元素,其中:

  • a1a_1 在栈顶;
  • a2a_2 在第二个位置;
  • …\dots;
  • aNa_N 在栈底。

接下来不断执行如下过程,直到栈中元素个数小于 22:

  1. 取出栈顶元素 top1⁡\operatorname{top1};
  2. 再取出新的栈顶元素 top2⁡\operatorname{top2};
  3. 将 $\operatorname{operation}(\operatorname{top1}, \operatorname{top2})$ 压回栈顶。

其中,operation⁡(x,y)\operatorname{operation}(x, y) 由你来决定,可以是:

  • 按位与:x&yx \mathbin{\&} y
  • 按位或:x∣yx \mathbin{|} y

也就是说,在每一步,你都可以自由选择当前操作是按位与还是按位或。

现在给定目标值 KK,你需要判断:是否存在一种操作方案,使得最终栈中只剩下一个数,并且它恰好等于 KK。

你需要处理 TT 组测试数据。

输入格式

第一行一个整数 TT,表示测试组数。

接下来每组测试数据包含两行:

  • 第一行两个整数 NN 和 KK;
  • 第二行 NN 个整数 a1,a2,…,aNa_1, a_2, \dots, a_N。

输出格式

对于每组测试数据:

  • 如果无解,输出一行 NO;
  • 如果有解,输出两行:
    • 第一行输出 YES;
    • 第二行输出一个长度为 N−1N-1 的字符串,表示每一步所选的操作,按实际执行顺序给出;
      • 若第 ii 个字符是 &,表示第 ii 步执行按位与;
      • 若第 ii 个字符是 |,表示第 ii 步执行按位或。

如果有多种方案,输出任意一种即可。

数据范围

  • 1≤T≤51 \le T \le 5
  • 1≤N≤1000001 \le N \le 100000
  • 0≤ai,K<2610 \le a_i, K < 2^{61}

部分分说明

  • 20% 的测试满足:N≤20N \le 20
  • 另外 30% 的测试满足:N≤1000N \le 1000,且 ai<211a_i < 2^{11}

样例

输入

3
4 5
7 4 2 6
4 7
7 4 2 6
4 3
7 6 5 11

输出

NO
YES
|||
YES
||&