Supermerge

Supermerge super works (joke lost in translation) like Tanaka would say, but it doesn't work because it has no legs (joke lost in translation). Recently, Andrei and Andrei discovered $N$ sets $S_1, S_2, \ldots, S_N$, which can contain only natural numbers from $1$ to $VMAX$. Initially, all sets are empty. On these sets, they observed the following operations occurring:

• flip poz val - if the element $val$ exists in the set $S_{poz}$, then we remove it from the set. Otherwise, we insert it.
• supermerge st1 dr1 st2 dr2 - the following is applied:

procedure Supermerge
    for i ← st1 ... dr1 do
        for j ← st2 ... dr2 do
        	S[i], S[j] ← S[i] ∪ S[j]

Requirement

Since the operations only cause chaos in the heads of the two Andreis, they want to know how many elements are in each set, after each operation. To simplify the result, they only ask for the computation of the following sum: $(|S_1| + |S_2| \cdot \text{mod} + |S_3| \cdot \text{mod}^2 + \ldots + |S_N| \cdot \text{mod}^{N-1}) \ \% \ 2^{64}$, where $\text{mod} = 10^9 + 7$.

Implementation Details

You will need to implement several functions. The first of them is:

void init(int N, int VMAX)

which receives as parameters:

• $N$, the total number of sets
• $VMAX$, the maximum value an element of a set can take

std::uint64_t flip(int poz, int val)

which:

• receives as parameters the index of the set and the value
• returns the sum describing the sets

std::uint64_t supermerge(int st1, int dr1, int st2, int dr2)

which:

• receives as parameters the intervals between which the supermerge operation takes place
• returns the sum describing the sets

The init function will be called exactly once, and the flip and supermerge functions will be called a total of at most $Q$ times.

Constraints and Notes

• $1 \leq Q \leq 1 \ 000 \ 000$
• $1 \leq N \cdot VMAX \leq 1 \ 000 \ 000$
• For any operation of type flip, it is guaranteed that $1 \leq poz \leq N$ and $1 \leq val \leq VMAX$
• For any operation of type supermerge, it is guaranteed that $1 \leq st1 \leq dr1 \leq N$ and $1 \leq st2 \leq dr2 \leq N$
• By S[i], S[j] ← S[i] ∪ S[j] we denote that both sets receive the result of the union of the two sets simultaneously.

Examples

input

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

output

1
1000000015000000057
2000000029000000106
4173964637407773643
4173964638407773650

Explanation

The state of the sets, after each operation, is:

1. $S_1 = \{1\}, \ S_2 = \emptyset, \ S_3 = \emptyset, \ S_4 = \emptyset, \ S_5 = \emptyset$
2. $S_1 = \{1\}, \ S_2 = \{1\}, \ S_3 = \{1\}, \ S_4 = \emptyset, \ S_5 = \emptyset$
3. $S_1 = \{1\}, \ S_2 = \{1\}, \ S_3 = \{1, 2\}, \ S_4 = \emptyset, \ S_5 = \emptyset$
4. $S_1 = \{1\}, \ S_2 = \{1\}, \ S_3 = \{1, 2\}, \ S_4 = \emptyset, \ S_5 = \{1\}$
5. $S_1 = \{1\}, \ S_2 = \{1, 2\}, \ S_3 = \{1, 2\}, \ S_4 = \emptyset, \ S_5 = \{1\}$