Marble Parity Strategy

Bessie and Elsie are playing a marble game. Initially, Elsie has N marbles. There will be M rounds left before Bessie quits. In each round i, Bessie will secretly choose a number of marbles A from a set S_i (of size K where 1 ≤ K ≤ 4). Elsie must guess whether A is even or odd by announcing either E (for even) or O (for odd).

The rules in each round are as follows:

• If Elsie’s guess is correct (that is, the parity of A matches her guess), she wins A marbles (so her count increases by A).
• If her guess is incorrect (the parity does not match), she loses A marbles. (Note: if she has fewer than A marbles at that moment, she loses all her marbles and loses the game.)

Elsie, who only wants to avoid losing, has observed that in round i the possible values chosen by Bessie come from a known set S_i. She wishes to precompute a strategy – that is, a fixed sequence of guesses (a string of length M consisting of letters ‘E’ and ‘O’) – such that no matter which values Bessie chooses each round, Elsie will never lose all her marbles (i.e. her marble count remains at least 1 at all times).

Moreover, among all strategies guaranteeing safety, Elsie wants the lexicographically smallest one (with the ordering E < O).

Important details and mechanics:

Assume that before the remaining rounds, Elsie’s current marble count is exactly N (1 ≤ N ≤ 10⁹). In each round, if Elsie has x marbles at the start, and she chooses a guess, the adversarial (worst‐case) outcome is:

• If her guess is E and the allowed moves S_i contain any odd numbers, then Bessie may choose a number with odd parity. In that case the outcome is x − d, where d is the maximum odd number in S_i. It is required that x ≥ d (so that x − d is nonnegative) and ultimately x − d ≥ 1.
• If S_i does not contain any number of the opposite parity then the outcome is forced; for example, if Elsie chooses E and S_i contains only even numbers, then the outcome is x + c, with c being the minimum number in S_i.
• A similar rule applies if Elsie chooses O. In that case, if S_i contains any even numbers, the worst‐case outcome is x − d with d equal to the maximum even number in S_i; otherwise the outcome is x + c, where c is the minimum number in S_i.

Your task is to compute the lexicographically smallest string of length M (with letters E and O) which represents a pre‐committed guessing strategy for Elsie that guarantees, against any choices by Bessie from the given sets S₁, S₂, …, S_M, that Elsie will never drop to 0 marbles.

---

Input Format:

The first line contains two integers N and M.

Then follow M lines. The ith of these lines describes round i and begins with an integer K (1 ≤ K ≤ 4), followed by K distinct positive integers (each ≤ 10⁹) representing the possible number of marbles Bessie might choose in that round.

---

Output Format:

Output a single string of length M consisting only of the characters E and O – the lexicographically smallest safe guessing strategy for Elsie. It is guaranteed that under the problem constraints a safe strategy exists.

inputFormat

The first line contains two space‐separated integers: N (the number of marbles Elsie currently has) and M (the number of rounds remaining).

Each of the next M lines starts with an integer K (1 ≤ K ≤ 4), the number of possible moves for that round, followed by K distinct positive integers representing the possible marble counts Bessie might pick in that round.

outputFormat

Output a single string of length M consisting of characters E and O – the lexicographically smallest sequence of guesses that ensures Elsie never loses (i.e. her marble count stays at least 1 in every round no matter what Bessie does).

sample

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

EEE