Yet Another Contest 5 P2 - Big Score

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

Josh, Nils, and Mike are on a heist!

They have already broken into T different banks. Each bank has three rooms, and each room in the k-th bank contains an array of N vaults. Originally, the i-th vault in all three rooms contained the same number of treasures.

Josh, Nils, and Mike coordinated their heist, so for every bank, each person went to a different room and performed exactly K moves on the vaults, where K is a positive integer (that may differ depending on the bank). However, despite their planning, each person made different types of moves.

  • In one move, Josh took exactly two treasures from vault i and put one treasure into vault j, where 1 \le j < i \le N.

  • In one move, Nils took exactly two treasures from vault i and put one treasure into vault j, where 1 \le i < j \le N.

  • In one move, Mike took either one or two treasures from any vault i, where 1 \le i \le N.

Of course, the number of treasures taken from a vault in one move could not exceed the number of treasures already in that vault.

Knowing this and given the final states of each vault inside of each room, can you help figure out which person broke into which room for each bank? Note that since they disabled the security cameras, you do not know the value of K.

Constraints

1 \le T \le 5\times10^5

2 \le N \le 10^6

0 \le a_i, b_i, c_i \le 10^{15}

It is guaranteed that each vault initially had no more than 10^9 treasures.

It is guaranteed that the input is valid. (Originally, a = b = c, and each person performed K (1 \le K) valid moves described above on a different array of vaults.)

The sum of N across all banks will not exceed 10^6.

Subtask 1 [15%]

N = 2

Subtask 2 [15%]

For every move, Mike is guaranteed to have removed two treasures.

Subtask 3 [70%]

No additional constraints.

Input Specification

The first line contains an integer T.

The next 4T lines contain information on the banks. For each bank, the first line contains an integer N.

The second line contains N integers a_1, a_2, \dots, a_N, representing the final state of the vaults inside the first room.

The third line contains N integers b_1, b_2, \dots, b_N, representing the final state of the vaults inside the second room.

The fourth line contains N integers c_1, c_2, \dots, c_N, representing the final state of the vaults inside the third room.

Output Specification

For each bank, on a separate line, output the names Josh, Nils, and Mike in an order corresponding to who broke into the first, second and third rooms respectively. If there are multiple possible valid orders, output any of them.

Sample Input

2
5
4 4 0 7 3
3 6 2 6 0
4 7 2 5 0
2
999999999 0
0 999999999
666666666 0

Sample Output

Nils Mike Josh
Josh Nils Mike

Explanation

Originally, the treasures inside the vaults of each room in bank 1 were [4, 6, 2, 9, 0], and each person performed K = 3 moves.

In the first room, Nils took two treasures from vault 2 and put one treasure back in vault 5, took two treasures from vault 3 and put one treasure back in vault 5, then took two treasures from vault 4 and put one treasure back in vault 5.

In the second room, Mike took one treasure from vault 1, took two treasures from vault 4, then took one more treasure from vault 4.

In the third room, Josh took two treasures from vault 4 and put one treasure back in vault 3, took two more treasures from vault 4 and put one treasure back in vault 3 once again, then took two treasures from vault 3 and put one treasure back in vault 2.


Comments

There are no comments at the moment.