Description

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

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

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

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

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

Format

Input

第一行三个正整数n，L，m。n是水题数目，m是管理员更改水题位置的数目。

接下来n个数，表示n道水题的初始位置。

接下来m行，每行两个数i(0<=i<n)，y(0<=y<=1000000000)。表示将第i+1道水题改到y（按输入顺序排名）。

Output

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

Samples

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

1
2
2
2
3

Limitation

对100%的数据满足，n，m <= 150000，L <= 1000000000。