版权声明

本题版权归 所有。

题目来源：https://www.luogu.com.cn/problem/T565374

题目背景

时间和空间交织错落，「神明」与幻影混杂凌乱。

题目描述

给你一个由 $n$ 个互不相同的整数 $\{s_n\}$ 组成的序列。

然后有 $m$ 次修改，每次在这个序列末尾插入原始序列 $[l_i,r_i]$ 中的所有数字。

接着有 $q$ 次询问，每次询问以第 $x_i$ 次插入的区间上值为 $t_i$ 的数字为开头的「好序列」最长长度。

注意，所有询问都是在插入完所有的区间后进行的。

「好序列」 $[l,r]$：满足 $[l,r]$ 中所有数字出现的次数 $\le k$。

输入格式

第一行四个整数 $n,k,m,q$。

第二行 $n$ 个整数 $\{s_n\}$。

之后 $m$ 行，每行两个整数 $l_i,r_i$。

再之后 $q$ 行，每行两个整数 $x_i,t_i$。

输出格式

共 $q$ 行，每行一个整数表示答案。

样例

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

样例 1 解释

• 一开始：$S_0= \{1,2,3,4\}$。
• 第一次操作后：$S_1= \{1,2,3,4,1,2\}$。
• 第二次操作后：$S_2= \{1,2,3,4,1,2,2,3,4\}$。

样例 2 解释

• 一开始：$S_0= \{6,7,8,1,2,3,4,5,2,3,4,5,6,7,8\}$。
• 第一次操作后：$S_1= \{1,2,3,4,5,2,3,4,5,6,7,8,6,7,8\}$。
• 最终：$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\}$。

数据范围

本题采用捆绑测试。

本题略微卡常，请注意程序常数级别的优化。

对于全部数据：

• $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$。