Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Europe Tour

By RobinHood3082 · Limits 1s, 256 MB

We, the members of CUET_Sapphire decided to have a tour in Europe. There are many countries in Europe, and because of European Union, there is no travel restriction among them (as our current knowledge). Each and every country is possible to travel from any other country. That’s why Ahasan, Shawly, and I decided to visit each and every country there is in Europe.

We could have visited them in any order we want. But that’s where the trouble began. We had different opinions about which country to visit after which. Ahasan said that country xx, then country yy, then country zz, was the right order. Shawly and I disagreed. Then Shawly gave us her own opinion. But Ahasan and I disagreed. Then the same thing happened when I suggested an order, but they disagreed. We are back to square one. 😐

We went to Himel vai and asked him what we can do about this. There are so many ways we could visit them. He said that it doesn’t matter in what order we visit and what route we take as long as we keep the total cost equal among us (😜). So we decided that all of us must visit all the countries exactly once (except for the starting country) using the same amount of total money (so that we don’t have disagreement over which route is better). He also suggested us to take different routes, so that we get to experience different and fun stuff along the road, and then share all our stories together when we return. We don’t have to keep the cost strictly equal. Himel vai will give us a number MM, we should keep our cost modulo MM, equal to each other.

So, the problem is, we don’t know how to do this (and we are lazy). There are NN countries (labeled from 11 to NN) in Europe, and Himel vai will give us a number MM. Each country xx has a beauty value AxA_x, which we know beforehand. We can travel between any two countries. The cost of travelling from country uu to country vv is AuAvA_u\oplus A_v Euros (‘\oplus’ represents Bit-wise XOR). Now, we hire you as a problem solver to help us with this issue. Please find us three different routes, each of which starts at country 11, then visits every other country exactly once, and returns to country 11; and such that each of these routes has equal cost (modulo MM). Cost of the route is the sum of Euros one has to spend for this route to complete visiting.

In this context, a route means a list of countries in a specific order of visit. For example, {1,3,2,1}\{1, 3, 2, 1\} is a route where we will start at country 11, then we’ll go to country 33 from here, then from here we’ll go to country 22, and then we’ll return to country 11.

Formally, find three routes PP, QQ and RR, such that -

P={1,P1,P2,P3,...,1}P = \{1, P_1, P_2, P_3, ..., 1\}

Q={1,Q1,Q2,Q3,...,1}Q = \{1, Q_1, Q_2, Q_3, ..., 1\}

R={1,R1,R2,R3,...,1}R = \{1, R_1, R_2, R_3, ..., 1\}

Here, each entry in the arrays PP, QQ and RR denotes a country in its order of visit in its respective route. Each route must be different from the other two. Each route must start and end at the country 11. cost(P) mod Mcost(Q) mod Mcost(R) mod Mcost(P)\ mod\ M \equiv cost(Q)\ mod\ M \equiv cost(R)\ mod\ M must satisfy, where cost(P)cost(P) denotes the cost of visiting countries in the order mentioned in route PP. Each route must contain every country. Each country must be visited exactly once (except for the first one).

Two routes XX and YY are different, if there is at least one ii such that XiYiX_i \neq Y_i.

Input

The first line of input contains an integer T(1T25000)T (1\leq T\leq 25000), denoting the number of test cases.

For each test case, there are two lines. The first line of each input contains two integers N(4N105)N (4\leq N\leq 10^5) and M(20M200)M (20\leq M\leq 200), denoting the number of countries in Europe and the number that you will use to denote modular equivalence.

The last line of each test case contains NN integers A1,A2,,AN (0Ai109)A_1, A_2, …, A_N\ (0\leq A_i\leq 10^9), the beauty value of each country.

It is guaranteed that sum of NN over all test cases will not be greater than 10510^5.

Output

For each testcase, print “No”\texttt{“No”} (without quotes) in a line if it is not possible to find three different routes which have the same total cost (modulo MM).

If it’s possible, print “Yes”\texttt{“Yes”} (without quotes). In the next three lines, print your three routes. Each route should contain N+1N+1 integers separated by space, and will start with country 11 and end with country 11, which denotes the order you intend us to visit the countries. Total cost of these three routes must be equal (modulo MM). We need to visit every country (except for the starting country) exactly once.

Sample

InputOutput
2
4 20
0 1 1 0
4 30
5 3 1 7
Yes
1 2 3 4 1
1 3 2 4 1
1 4 2 3 1
No

    Discussion

    Statistics


    75% Solution Ratio

    YouKnowWhoEarliest, 1M ago

    YouKnowWhoFastest, 0.0s

    nskybytskyiLightest, 2.4 MB

    Deshi_TouristShortest, 1003B

    Submit

    Login to submit

    Editorial

    Prerequisites: Pigeonhole Principle knowing how to check permutations of an array how modular ...