War - Land Grab

Interview

Time limit10sMemory limit512 MB

Summary

For each region's list of soldier army IDs, find the majority element that appears more than half the time, or print SYJKGW if none exists.

Level: Easy3 of 10
Topics: Array, Hash map
Solved: No attempts yet

Problem

A full-scale war has broken out, and several regions are being contested.

In each region, soldiers from several armies may be mixed together. Armies are identified only by integer army IDs instead of names.

If the soldiers with one army ID make up strictly more than half of all soldiers in a region, that army controls the region.

For each region, print the ID of the army that controls it. If no army controls the region, print SYJKGW.

Input

The first line contains the number of regions n. (n <= 200)

Each of the next n lines describes one region. The first integer on a line, T_i, is the number of soldiers in the i-th region. It is followed by T_i integers N_{ij}, where N_{ij} is the army ID of the j-th soldier in that region.

T_i <= 100,000, and |N_{ij}| <= 2^31.

Output

Print one line for each region, in input order.

If a region is controlled by an army, print that army ID. Otherwise, print SYJKGW.

Examples1

Example 1

Input

4
10 1 2 3 1 2 3 1 2 3 1
5 1 1 1 2 2
6 10 10 2 10 10 2
6 1 1 1 2 2 2

Expected output

SYJKGW
1
10
SYJKGW