Description

Natural used the following Fenwick-tree update function to maintain an array $a_1,a_2,\ldots,a_n$. Initially, every element of the array is $0$.

void add(int x, int k)
{
    for (; x <= n; x += (x & -x))
        a[x] += k;
}

Larutan thought that the add(x, k) function was elegant, so he discarded the rest of the Fenwick tree and kept only this function.

Natural must now process the following two types of operations:

1. 1 x k: Call add(x, k).
2. 2 l r: Calculate $\left(\sum\limits_{i=l}^{r}a_i\right)\bmod 2^{64}$.

The operations are not listed directly in the input. Instead, they are generated by the following code. The variables s1 and s2 are initialized using the values provided in the input.

#define ull unsigned long long
ull s1, s2;

ull my_rand()
{
    ull s3 = s1, s4 = s2;
    s1 = s2 ^ 774527;
    s3 ^= (s3 << 47) ^ (s3 >> 13);
    s2 ^= s3 ^ (s4 << 31) ^ (s4 >> 17);
    return s2 + s4;
}

void get_query(int &op, ull &num1, ull &num2)
{
    op = my_rand() % 2 + 1;
    if (op == 1)
    {
        num1 = my_rand() % n + 1;
        num2 = my_rand() % n + 1;
    }
    else
    {
        num1 = my_rand() % n + 1;
        num2 = my_rand() % n + 1;
        if (num1 > num2)
            swap(num1, num2);
    }
}
#undef ull

Call get_query exactly $Q$ times and process the generated operations in order. Interpret the returned values as 1 num1 num2 when op == 1, and as 2 num1 num2 when op == 2. Thus, num1 and num2 represent $x$ and $k$ in a type-1 operation, or $l$ and $r$ in a type-2 operation. The operations are numbered from $1$ to $Q$.

Suppose the type-2 operations occur at operation indices $id_1,id_2,\ldots,id_k$, and their respective answers are $ans_1,ans_2,\ldots,ans_k$. Output

$$\bigoplus_{i=1}^{k}\left((id_i\times ans_i)\bmod 2^{64}\right), $$

where $\oplus$ denotes bitwise XOR. If there are no type-2 operations, output $0$.

All arithmetic on values of type unsigned long long, including overflow in the random number generator, follows modulo $2^{64}$ arithmetic.

Input Format

The input contains four integers $n$, $Q$, $s1$, and $s2$. They represent the array length, the number of generated operations, and the two initial states of the random number generator, respectively.

Output Format

Output the checksum defined above on one line.

Samples

Input #1

5 5 1919810 114514

Output #1

20

Input #2

9129 9579 7637383388378987721 14219202285634227728

Output #2

1234650488382

Constraints

For all test cases:

• $1\leq n,Q\leq 10^7$;
• $0\leq s1,s2<2^{64}$.