Given a positive integer N, consider any permutation of all the numbers from 1 to N. It is required to create two partitions, P₁ and P₂, from these numbers such that |sum(P₁) – sum(P₂)| is minimum, where sum(X) denotes the summation of all the numbers in partition X. A partition is defined to be a non-empty subset of the permutation. In other words, find the minimum absolute difference between the summation of all the numbers in each partition. Note that you cannot leave out any number, every number from 1 to N must be part of exactly one partition.

To add a little bit more of spice, also find the lexicographically smallest partition P₁ such that |sum(P₁) – sum(P₂)| is minimum. To make your life easier, you don’t need to output the entire sequence, only the hash of the sequence as computed by the function below would suffice.

def sequence_hash(sequence, B, M):
   result = 0
   for number in sequence:
       result = (result * B + number) % M

   return result

Input

The first line contains an integer T, denoting the number of test cases. Each of the next subsequent T lines contain three positive integers, N, B and M.

Constraints

1 ≤ T ≤ 1000

2 ≤ N ≤ 10⁹

N < B ≤ 10⁹

1 ≤ M ≤ 10⁹

Output

For each test case, first print the case number followed by the minimum absolute difference and the hash of the lexicographically smallest partition P₁.

Sample Input

12
2 10 1000000000
3 10 1000000000
4 10 1000000000
5 10 1000000000
6 10 1000000000
7 10 1000000000
8 10 1000000000
9 10 1000000000
1000 1000000000 1000000
1000000 1003001 998244353
123456789 987654321 666666667
444444444 666666666 888888888

Sample Output

Case 1: 1 1
Case 2: 0 12
Case 3: 0 14
Case 4: 1 124
Case 5: 1 1234
Case 6: 0 1247
Case 7: 0 12348
Case 8: 1 123457
Case 9: 0 1000
Case 10: 0 553178755
Case 11: 1 214459309
Case 12: 0 557434257

Challenge

Don't like challenges? Try the easier version here:

Bipartite Permutation

---

hide comments

	khoaph: 2021-03-15 08:50:26 For the 4th case 5 10 1000000000 With n = 5, I found P1 = {1, 2 , 5}, P2 = {3, 4} So the smallest lexicographically partition P1 is { 1, 2, 5} The hash will be: H0 = 0; H1 = (0 *10 + 1)%1000000000= 1 H2 = (1 * 10 + 2)%1000000000 = 12 H3 = (12 * 10 + 5)%1000000000 = 125 So why the result in the example is 124 Am I misunderstanding something? [NG]: For n=5, smallest P1 is {1, 2, 4}. Last edit: 2021-03-15 15:14:13
	:D: 2019-11-19 09:13:42 Great problem. I really like how output is handled. It allowed for big N values and actually creates a sub-problem to solve. -> Thanks! Glad you liked it :D Last edit: 2019-11-23 20:45:43