Background

As the Year of the Dragon arrives, FanFan raises his colorful dragon lamp, and he himself is about to become a big colorful dragon!

Problem Description

FanFan has a total of $n$ dragon lamps, with the $i$-th lamp being of color $a_i$.

FanFan believes that the aesthetic value $f(l,r)$ of an interval $[l,r]$ is the number of distinct colors in $a_l \cdots a_r$.

FanFan plans to take his dragon lamps out to play for a total of $m$ days. On the $i$-th day, he will take his $1 \cdots x_i$ numbered dragon lamps. However, he realizes that if he groups many lamps together, others will only notice how many different colors are present.

Therefore, FanFan intends to divide these $x_i$ dragon lamps into exactly $k_i$ intervals in the order of their numbers, ensuring that each lamp is exactly in one interval.

The aesthetic value of FanFan's outing will then be the sum of the aesthetic values of all intervals.

Please help FanFan maximize the aesthetic value for each outing.

Input Format

The first line contains five integers $n, m, id, seed, limx$, representing the sequence length, the number of queries, the subtask ID (in the sample, $id=0$), the random number seed, and a parameter related to the queries, $limx$.

Due to the large input size, queries are generated as follows:

We use the following code to generate a pseudo-random sequence:

uint64_t PRG_state;
uint64_t get_number()
{
    PRG_state ^= PRG_state << 13;
    PRG_state ^= PRG_state >> 7;
    PRG_state ^= PRG_state << 17;
    return PRG_state;
}
int readW(int l,int r)
{
    return get_number()%(r-l+1)+l;
}

Initially, PRG_state=seed, and each call to readW(l,r) returns a random number in the range $[l,r]$.

The second line contains $n$ integers, with the $i$-th integer representing $a_i$.

Let $x_i, k_i, c_i$ denote the parameters $x, k, c$ required for the $i$-th query, where $c$ is described in the Output Format. The parameters for all queries are generated by the following program:

for (int i = 1; i <= m; ++i) {
    x[i] = readW(limx, n);
    k[i] = readW(1, x[i]);
    c[i] = readW(0, 1e7);
}

Note: Do not call the readW() function before running the above code segment to obtain the parameters for each query, otherwise, the correct query information cannot be obtained. This problem does not require the use of any special properties of the pseudo-random number generator. You can simply treat get_number() as a generator that independently and uniformly randomly generates an unsigned 64-bit integer each time. The internal implementation of the pseudo-random number generator does not need to be optimized for this problem.

Output Format

To reduce the output size, we use the following method for information compression:

If the answer for the $i$-th query is $ans_i$ with the generated parameter $c_i$, then you need to output:

$$\bigoplus\limits_{i=1}^m(ans_i \times c_i)$$

where $\bigoplus$ denotes the XOR operation, and this value is clearly within the range that can be represented by long long.

Sample Input and Output

Input Sample #1

5 5 0 956144375 1
2 4 1 5 2 

Output Sample #1

21971409

Input Sample #2

10 10 0 478178732 1
2 2 1 1 2 1 2 1 2 1 

Output Sample #2

2834792

Notes

Sample 1 Explanation

The queries are:

3 1 6121576
5 3 3089509
1 1 4506170
3 1 2821007
1 1 7941511

The answers are:

3
5
1
3
1

For the first query, to divide into one interval, it is $[1,3]$, and the aesthetic value is $f(1,3)=3$.

For the second query, the optimal plan is to divide into $[1,3],[4,4],[5,5]$, and the aesthetic value is $f(1,3)+f(4,4)+f(5,5)=5$.

The same logic applies to the last three queries.

Sample 2 Explanation

The queries are:

8 4 6858024
3 2 236530
2 2 8140891
5 3 4562139
8 7 4749403
7 4 4319971
5 1 5063575
3 1 7343109
6 2 1566851
3 1 7959241

The answers are:

7
3
2
5
8
7
2
2
4
2

Data Range

This problem uses bundled testing.

• Subtask 1 (10 points): $1 \leq n \leq 500$.
• Subtask 2 (15 points): $1 \leq n \leq 3000$.
• Subtask 3 (15 points): $m=1$.
• Subtask 4 (20 points): $1 \leq a_i \leq 30$.
• Subtask 5 (20 points): $1 \leq n \leq 4 \times 10^4$.
• Subtask 6 (20 points): No special restrictions.

For $100\%$ of the data, $1 \leq n \leq 10^5$, $1 \leq m \leq 10^6$, $0 \leq seed \leq 10^9$, $1 \leq limx \leq n$, $1 \leq a_i \leq n$.

见题面 Input 部分

见题面 Output 部分