#2902. 一道水题

内存限制:256 MiB 时间限制:20 Sec

题目描述

    话说世界上有很多被大神狂虐的水题,比如说上面第二题,在很久很久以前就被很多很多大神在某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<=i<n),y(0<=y<=1000000000)。表示将第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 <= 150000,L <= 1000000000。