Expert.
Put your skills to the test.

Problem summary

A stack has a1 at the top and aN at the bottom. Repeatedly combine the top two values using either bitwise AND or bitwise OR, chosen independently for each operation, until one value remains. Determine whether it can equal K and output a valid operation string.

Constraints

1 ≤ T ≤ 5; 1 ≤ N ≤ 100000; 0 ≤ ai,K < 2^61.

Worked example

Official example, transcribed with whitespace restored from the PDF.

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

NO
YES
|||
YES
||&

Solution analysis

1. The computation is a left fold: after handling a1,…,ai, combine that accumulator with a(i+1). Work backward, tracking only the bit positions whose required final values have not yet been forced by the suffix. AND is legal unless an active target-one bit is zero in ai; after choosing it, only active bits where ai is one remain relevant. OR is legal unless an active target-zero bit is one in ai; afterward only active bits where ai is zero remain relevant.
2. If exactly one operation is legal, it is forced. If neither is legal, the instance is impossible. If both are legal, ai equals K on all active bits. Choosing AND then immediately fixes all target-zero bits, leaving only target-one requirements on the preceding prefix; the bitwise OR of that whole prefix satisfies them whenever any prefix expression can. Alternatively, choosing OR fixes all target-one bits, and the bitwise AND of the prefix is the best possible way to satisfy its target-zero requirements. Precompute prefix OR and prefix AND to test these alternatives instantly.
3. When an alternative succeeds, fill its earlier operations uniformly with OR or AND and keep the already fixed suffix. If no branch point appears, check a1 on the remaining active bits. In the third sample, (7 OR 6 OR 5) AND 11 equals 3.

Why it works

The reverse legality tests are exactly the one-bit truth tables for AND and OR; removing bits whose result is already forced preserves precisely the remaining requirements. A sole legal operation is therefore mandatory. At a two-choice point, the AND branch leaves only required ones; prefix OR is a superset of the one-bits of every possible prefix expression, making it a complete feasibility test. The OR branch leaves only required zeros; prefix AND is a subset of the one-bits of every prefix expression, also making it complete. Both branches together cover every possible operation at that point. Hence every accepted construction evaluates to K and every rejection is impossible.

Watch out. The expression is left-associated in input order. Do not choose an arbitrary branch when both backward operations are legal.

An independently written complete program with standard headers.

// Key idea: The reverse legality tests are exactly the one-bit truth tables for AND and OR; removing
// bits whose result is already forced preserves precisely the remaining requirements. A sole legal
// operation is therefore mandatory.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
using U64=unsigned long long;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests;
    cin>>tests;
    while(tests--){
        int n;
        U64 target;
        cin>>n>>target;
        vector<U64>a(n),prefixOr(n),prefixAnd(n);
        for(int i=0;i<n;++i){
            cin>>a[i];
            prefixOr[i]=a[i]|(i?prefixOr[i-1]:0);
            prefixAnd[i]=a[i]&(i?prefixAnd[i-1]:~U64(0));
        }
        U64 mask=(U64(1)<<61)-1;
        string operations(n-1,'&');
        bool valid=true,finished=false;
        for(int i=n-1;i>=1;--i){
            bool canAnd=(mask&target&~a[i])==0;
            bool canOr=(mask&~target&a[i])==0;
            if(!canAnd&&!canOr){
                valid=false;
                finished=true;
                break;
            }
            if(canAnd&&canOr){
                if((mask&target&~prefixOr[i-1])==0){
                    for(int j=0;j<i-1;++j){
                        operations[j]='|';
                    }
                    operations[i-1]='&';
                }
                else if((mask&~target&prefixAnd[i-1])==0){
                    for(int j=0;j<i-1;++j){
                        operations[j]='&';
                    }
                    operations[i-1]='|';
                }
                else{
                    valid=false;
                }
                finished=true;
                break;
            }
            if(canAnd){
                operations[i-1]='&';
                mask&=a[i];
            }
            else{
                operations[i-1]='|';
                mask&=~a[i];
            }
        }
        if(!finished){
            valid=((a[0]^target)&mask)==0;
        }
        if(valid){
            cout<<"YES\n"<<operations<<'\n';
        }
        else{
            cout<<"NO\n";
        }
    }
}