蛋糕這學期開了一門神奇的課程，評分方式完全看個人運氣(噢終於不用寫code了!)。蛋糕準備了一疊N張上面標有整數的紙牌，編號1~N，每個人可以任意挑選兩個數字A和B(A<=B)，第A張牌到第B張牌的總和(包含A和B)就是你的得分。可是蛋糕如果直接把這個成績交給學校，他一定會被解聘QQ所以他想出了一個評分方式:大家排隊依序選好A和B之後，如果你的得分比K個以上(含)在你後面選牌的人大，那你就可以得A+，否則將會被當掉。
可能你是一個運氣很背猜拳從來沒贏過的人，在這種評分方式下有99.99999%的機率會被當;可能你是排在隊伍最後的人，不管得到多高的分數，100%會被當；可能蛋糕非常陰險讓所有人分數都一樣，這樣全班都會被當。
蛋糕很好心的想拯救大家，所以他給你們一個機會。如果你能寫出一個程式快速地告訴他全班有幾個人能夠得到A+，雖然他還是不會讓你過，但他會願意幫你簽二退單。
唉，終究還是得寫code。
有多組測資，每組測資第一列為三個正整數N, Q, K。N代表牌的數量，接下來N個整數代表第1張牌到第N張牌上面的點數。
接著會有Q列，每列有兩個數字A,B，分別代表第1個學生到第Q個學生選的數字。
1<=N<=1000000
1<=Q<=1000000
1<=K<=Q
1<=A<=B<=N
-100<=牌的點數<=100
針對每組測資輸出一個整數，代表可以得到A+的人數。