题目描述

话说世界上有很多被大神狂虐的水题，比如说上面第二题，在很久很久以前就被很多很多大神在某 OJ 上直接 AC。本题也是一道水题，自从 2012 年二月份以来，全国的 Oier 就没有没在半小时之内水过这道题的。

其实本题就是这么一道水题：话说某题库，在某些神题中掺了很多道水题，一位大神突发奇想，想在尽可能短的时间内把水题全部 AC。大神一般是这么做题的，他会在一秒钟之内把第 $i$ 题到第 $i+l$ 题全部 AC。大神早就把水题的分布全都摸透了，所以说水题被切是其从诞生起就注定了的命运。不过大神还有别的神题去做，没有太多时间花在水题上，所以他得在尽可能少的时间内将水题切完。为了合理安排水题的切题计划，大神写了个程序来规划。

但题库的管理员恶意地想拖慢大神刷水题的速度，于是他老是更改水题的位置，试图使大神的程序判断失误，从而延误大神的时间。当然了，大神的程序是无敌的，管理员每更改水题的位置，大神的程序多可以在极短的时间内判断出大神切水题的时间。而本题也就是这么个问题。

你就是那位大神——湖南 Oier 中的精英。你得为你的切水题计划重新写一个程序了。当然，作为大神的你自然不屑于做这种水题。你可以选择不做此题，而在程序中打出「I am a godlike cowcowcow!」，从而积蓄 RP，在 NOI 上虐爆全场吧！

注意，管理员可没有保证水题不会在一个位置重合。

输入格式

• 第一行三个正整数 $n,l,m$。$n$ 是水题数目，$m$ 是管理员更改水题位置的数目。
• 接下来 $n$ 个数，表示 $n$ 道水题的初始位置。
• 接下来 $m$ 行，每行两个数 $i$（$0\le i< n$），$y$。表示将第 $i+1$ 道水题改到 $y$（按输入顺序排名）。

输出格式

• 输出共 $m$ 行，表示第 $i$ 次管理员改变水题的位置后大神切题所需时间（以秒为单位）。

4 10 5
10 15 17 20
2 16
1 25
3 35
0 38
2 0

1
2
2
2
3

数据规模与约定

对 $100\%$ 的数据，$n,m \le 1.5\times 10^5$，$l \le 10^9$，$0\le y\le 10^9$。