F. Find the Fake
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider this classic riddle. There are $$$n$$$ coins (labeled $$$1$$$ to $$$n$$$), and exactly one among them is fake. All real coins weigh $$$2$$$ grams, whereas the fake coin weighs $$$1$$$ gram. Then, $$$q$$$ times, you may do the following: Choose any subset of the coins and put them in a weighing scale, giving you the total mass of this selection of coins (in grams).

You know how to solve this problem right? Of course you do. Unfortunately, Bob doesn't, and he may have squandered all his guesses.

After using the weighing scale $$$q$$$ times, he called in Alice for help, who was made aware of all the queries that Bob made (and the respective responses to each one). Once she was done processing all this information: one-by-one, Bob pointed at each coin on the table and asked her, "Is this coin the fake one?" For each of these, Alice (who is honest and a perfect logician) answered one of: Yes, No, or Maybe. In the end, how many times did Alice end up saying each of these responses?

It is guaranteed that all values given by the weighing scales are correct, and corresponds to a valid sequence of responses in the scenario posed by the original riddle.

Input

The first line of input contains the two space-separated integers $$$n$$$ and $$$q$$$.

Then, the descriptions of Bob's queries follow. Each query is described by three lines:

  • The first line contains some positive integer $$$k_i$$$, the number of coins Bob put into the weighing scale in this query.
  • The second line contains $$$k_i$$$ distinct positive integers, the labels of the coins put into the weighing scale in this query.
  • The third line contains a single positive integer, the total mass of those coins.
Output

Output three space-separated integers, corresponding to the number of times that Alice said Yes, No, and Maybe, respectively.

Scoring

Let $$$K$$$ be the sum of $$$k_i$$$ across all queries.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq n \leq 10^9 \\ 1 \leq K \leq 2\cdot 10^5 \\ \text{$1 \leq k_i \leq n$ in each query} \\ \text{The chosen coins are distinct, in each query.} \\ \text{The responses are guaranteed to all be correct.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & \text{$k_i = 1$ in each query} \\ \hline 2 & \mathbf{30} & n, K \leq 2000 \\ \hline 3 & \mathbf{20} & n \leq 2 \cdot 10^5 \\ \hline 4 & \mathbf{30} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Examples
Input
4 2
2
1 2
3
3
1 3 4
5
Output
1 3 0
Input
10 2
3
1 2 3
6
2
4 5
4
Output
0 5 5