410673: GYM104072 K Teams

There are only a few hours left before the AGM finals and still many problems to complete. Currently there are $$$N$$$ members in the jury numbered from $$$0$$$ to $$$N - 1$$$ and so far neither of them has completed any problem. In order to increase their productivity and to better keep track of the finished problems, the members of the scientific committee have decided to split into several teams.

Over the course of the night there are 2 main events that can happen:

1. a new team, consisting of members $$$i_1$$$, $$$i_2$$$, ..., $$$i_k$$$, is formed and is responsible for completing at least $$$C$$$ problems.
2. the member $$$i$$$ creates $$$P$$$ new problems.

After each event of the $$$2^{nd}$$$ type the jury is wondering how many of the already formed teams have finished their job.

Please note that one member of the jury can be part of multiple teams, and all the problems he develops will contribute to all the teams that he belongs to.

The first line of the input contains the integers $$$N$$$ ($$$1 \leq N \leq 200.000$$$) and $$$Q$$$ ($$$1 \leq Q \leq 200.000$$$), denoting the number of members of the jury and the number of events that happen during the night. The next $$$Q$$$ lines have the following structure:

• $$$type'$$$ $$$C'$$$ $$$k'$$$ $$$i_1'$$$, ..., $$$i_k'$$$
• $$$type'$$$ $$$i'$$$ $$$P'$$$

In order to retrieve the actual parameters of the operation you have to xor each one of them with $$$last\_answer$$$, where $$$last\_answer$$$ is the most recent result of a query (initially $$$last\_answer$$$ is set to 0). The decoded lines will look as follows:

• $$$1$$$ $$$C$$$ $$$k$$$ $$$i_1$$$, ..., $$$i_k$$$
• $$$2$$$ $$$i$$$ $$$P$$$

where $$$0 \leq C, P \leq 1.000.000$$$, $$$1 \leq k \leq 3$$$ and $$$0 \leq i, i_1, .., i_k \leq N - 1$$$ ($$$i_1$$$, ..., $$$i_k$$$ are distinct)

For each operation of the $$$2^{nd}$$$ type print the number of teams that finished their job.

3 6
1 2 2
0 1
2 0 1
2 1 1
0 4 2
1 0 3
3 3 2
0 2 3

0
1
2
2

Decoded version of the sample:

3 6 1 2 2 0 1 2 0 1 2 1 1 1 5 3 0 1 2 2 2 3 2 0 1