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 , then country , then country , 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 , we should keep our cost modulo , equal to each other.
So, the problem is, we don’t know how to do this (and we are lazy). There are countries (labeled from to ) in Europe, and Himel vai will give us a number . Each country has a beauty value , which we know beforehand. We can travel between any two countries. The cost of travelling from country to country is Euros ( 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 , then visits every other country exactly once, and returns to country ; and such that each of these routes has equal cost (modulo ). 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, is a route where we will start at country , then we’ll go to country from here, then from here we’ll go to country , and then we’ll return to country .
Formally, find three routes , and , such that
Here, each entry in the arrays , and 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 . must satisfy, where denotes the cost of visiting countries in the order mentioned in route . Each route must contain every country. Each country must be visited exactly once (except for the first one).
Two routes and are different, if there is at least one such that .
The first line of input contains an integer , denoting the number of test cases.
For each test case, there are two lines. The first line of each input contains two integers and , 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 integers , the beauty value of each country.
It is guaranteed that sum of over all test cases will not be greater than .
For each testcase, print (without quotes) in a line if it is not possible to find three different routes which have the same total cost (modulo ).
If it’s possible, print (without quotes). In the next three lines, print your three routes. Each route should contain integers separated by space, and will start with country and end with country , which denotes the order you intend us to visit the countries. Total cost of these three routes must be equal (modulo ). We need to visit every country (except for the starting country) exactly once.
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
Login to submit
Prerequisites: Pigeonhole Principle knowing how to check permutations of an array how modular ...