Source

This problem is proposed by . All rights reserved.

Problem Source: https://www.luogu.com.cn/problem/T565374

Problem Background

Time and space intertwine chaotically, where "deities" blend with illusions.

Problem Description

You are given a sequence $\{s_n\}$ consisting of $n$ distinct integers.

There are $m$ modification operations, each inserting all numbers from the original sequence's interval $[l_i, r_i]$ at the end of the current sequence.

Then, there are $q$ queries. Each query asks for the maximum length of a "good sequence" starting with the number $t_i$ on the interval inserted in the $x_i$-th operation.

Note that all queries are performed after all insertions are completed.

A "good sequence" $[l, r]$ satisfies that the count of every number in $[l, r]$ is $\le k$.

Input Format

The first line contains four integers $n, k, m, q$.

The second line contains $n$ integers $\{s_n\}$.

The next $m$ lines each contain two integers $l_i, r_i$.

The following $q$ lines each contain two integers $x_i, t_i$.

Output Format

Output $q$ lines, each containing one integer as the answer.

Samples

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

4

8 2 4 2
1 2 3 4 5 6 7 8
1 5
2 8
6 8
3 6
1 1
0 6

15
15

3 1 1 1
76546 39549 18452
1 1
0 18452

2

Sample 1 Explanation

• Initial sequence: $S_0= \{1,2,3,4\}$.
• After the first operation: $S_1= \{1,2,3,4,1,2\}$.
• After the second operation: $S_2= \{1,2,3,4,1,2,2,3,4\}$.

Sample 2 Explanation

• Initial sequence: $S_0= \{6,7,8,1,2,3,4,5,2,3,4,5,6,7,8\}$.
• After the first operation: $S_1= \{1,2,3,4,5,2,3,4,5,6,7,8,6,7,8\}$.
• Final sequence: $S_4= \{1,2,3,4,5,6,7,8,1,2,3,4,5,2,3,4,5,6,7,8,6,7,8,3,4,5,6\}$.

Data Range

This problem uses bundled tests.

The problem is slightly time-sensitive, so please optimize your code for efficiency.

For all data:

• $1\le n,m,k\le2\times10^5$.
• $1\le q\le3\times10^5$.
• $1\le l_i\le r_i\le n$.
• $1\le s_i,t_i\le10^9$.