题目背景

由于「神」被卡常了，于是决定卡卡别人。

题目描述

现在「神」出了一道数据结构题。

给你一个长度为 $n$ 的整数序列 $a$，并保证 $\forall i\in[1,n],a_i\in[1,m]$。 你需要使用 odt 进行 $q$ 次神奇的操作，每次操作的对象是 $[l_i,r_i]$。

众所周知，odt 的时间复杂度是基于区间颜色段数量的，不妨假设每次操作的复杂度为区间极长连续相同颜色段的数量，即对于 $[l,r]$，其复杂度为 $1+\sum_{i=l+1}^r[a_{i-1}\neq a_i]$，其中的“ $[\ ]$ ”为艾弗森括号。

由于「神」喜欢卡常，作为数据制作人的你希望能够让所有 odt 操作的复杂度之和尽可能地大，因此你决定把「神」给你的序列中 $k$ 个元素改为 $[1,m]$ 中的某几个数。

当然，「神」想要知道你能把 odt 卡成什么样子。你需要对于每个 $k\in[0,T]$，给出更改后其所有操作的复杂度之和的最大值。

输入格式

第一行 $4$ 个整数 $n,m,T,q$。 第二行 $n$ 个整数，第 $i$ 个整数为 $a_i$。 接下来 $q$ 行，每行 $2$ 个整数 $l_i,r_i$。

输出格式

共 $T+1$ 行，第 $i$ 行为 $k=i-1$ 时的答案。

11 3 3 4
1 1 2 1 2 3 1 1 1 2 2
2 6
3 11
5 9
8 11

16
21
23
23

4 3 2 1
2 2 2 2
1 3

1
3
3

提示

样例 1 解释

$k=0$ 时，所有操作的复杂度之和最大为 $5+6+3+2=16$。
$k=1$ 时，修改 $a_8\leftarrow 3$ 是一种最优的方案，此时的答案为 $5+8+5+3=21$。
$k=2$ 时，修改 $a_{11}\leftarrow 1,a_{8}\leftarrow 2$ 是一种最优的方案，此时的答案为 $5+9+5+4=23$。

数据范围

本题采用捆绑测试。

• Subtask 1（15 pts）：$n,q\le 10$，$m=3$。
• Subtask 2（5 pts）：$\forall i\in[2,n],a_i\neq a_{i-1}$。
• Subtask 3（10 pts）：$T=0$。
• Subtask 4（30 pts）：$n\le 5000$。
• Subtask 5（10 pts）：$\forall i\in[2,n],a_i= a_{i-1}$。
• Subtask 6（30 pts）：无特殊限制。

对于所有数据，$1\le n,q\le 2\times 10^5$，$0\le T\le n$，$3\le m\le2\times 10^5$，$1\le a_i\le m$，$1\le l_i\le r_i\le n$。