bee 2849 - Rangel and the Array Game II

Always after the programming competitions the participants usually interact. Thinking about it, Rangel is developing an interesting game for the participants to play after a competition. This game will be known as the Array Game.

The Array Game works as follows:

A array with N integers is generated randomly and shown for 10 seconds for the challengers.
Then follows Q rounds where players must say how many times the Kth smaller element appears in a given range.
Win the round closest to the result.

This year Rangel called his friends Gugu and Dabriel to test the new game and asked you to design the judge to say who Kth is their frequency in the break and who wins the ith round.

Input

In the first line consists of two integers N and Q (1 ≤ N, Q ≤ 10⁵) representing the size of the array. The next line contains N integers Xi (-2³²+1 ≤ Xi ≤ 2³²-1) which are the elements of the array. The next Q lines contain five integers L and R (1 ≤ L ≤ R ≤ N) representing the extremes of the round interval, K which is the smaller Kth element drawn (Kth will always exist), G and D (1 ≤ G, D ≤ 2³²-1) the guess of Gugu and Dabriel respectively.

Output

For each round you should print an integer X that is the smallest Kth, an integer Y that indicates how many times the smallest Kth appears in the range and a character C that should be:

G case Gugu wins;
D case Dabriel wins;
E case of a draw.

Input Sample	Output Sample
10 5 1 4 5 2 7 4 5 8 10 1 1 10 1 3 1 1 5 2 1 4 2 6 3 1 1 7 7 1 0 10 3 8 4 10 4	1 2 E 2 1 G 4 2 E 5 1 G 5 2 D