Background

The Year of the Dragon has arrived, and Fanfan has also raised his own colorful dragon lantern. He wants to become a big colorful dragon too.

Problem Description

Fanfan has a total of $n$ dragon lanterns. The color of the $i$-th lantern is $a_i$.

Fanfan defines the beauty value $f(l,r)$ of an interval $[l,r]$ as the number of distinct colors in $a_l \cdots a_r$.

Fanfan is going out to have fun with his dragon lanterns. He plans to go out for $m$ days. On day $i$, he will bring lanterns No. $1 \cdots x_i$. However, he finds that if many lanterns are bundled together, others will only notice how many different colors there are.

So Fanfan plans to divide these $x_i$ lanterns, in order of their indices, into exactly $k_i$ intervals, such that each lantern belongs to exactly one interval.

Then the beauty value of this trip is the sum of the beauty values of all intervals.

Please help Fanfan maximize the beauty value for each trip.

Input Format

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

Because the input size is too large, the queries are generated in the following way.

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. Each time you call readW(l,r), it returns a random number within $[l,r]$.

The second line contains $n$ integers, where the $i$-th integer represents $a_i$.

Let $x_i,k_i,c_i$ be the parameters $x,k,c$ needed for the $i$-th query, where the role of $c$ is described in the output format. Then all query parameters can be 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 readW() before running the code snippet above to obtain the parameters for each query, otherwise you will not get the correct query information. This problem does not require using any special property of this pseudo-random generator. You only need to treat get_number() as a generator that independently and uniformly produces an unsigned $64$-bit integer each time it is called. This problem also does not require optimizing the internal implementation of the pseudo-random generator.

Output Format

To reduce the amount of output, we use the following compression method.

If the answer to the $i$-th query is $ans_i$, and its generation parameter is $c_i$, then you need to output:

where $\bigoplus$ denotes the bitwise XOR operation. This value is guaranteed to be within the integer range representable by long long.

5 5 0 956144375 1
2 4 1 5 2 

21971409

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

2834792

Hint

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, it must be divided into one interval, so it is $[1,3]$, and the beauty 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 beauty value is $f(1,3)+f(4,4)+f(5,5)=5$.

The last three queries are similar.

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 query answers are:

7
3
2
5
8
7
2
2
4
2

Constraints

This problem uses bundled testdata.

• 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\le a_i\le 30$.
• Subtask 5 ($20$ points): $1\leq n\leq 4\times 10^4$.
• Subtask 6 ($20$ points): No special restrictions.

For $100\%$ of the testdata, $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$。

Translated by ChatGPT 5