【分塊·莫隊】作詩

Time Limit:30000MS Memory Limit:131072K Case Time Limit:3000MS

Description

神犇SJY虐完HEOI之后給傻×LYD出了一題： SHY是T國的公主，平時的一大愛好是作詩。 由于時間緊迫，SHY作完詩之后還要虐OI，于是SHY找來一篇長度為N的文章，閱讀M次，每次只閱讀其中連續的一段[l,r]，從這一段中選出一些漢字構成詩。因為SHY喜歡對偶，所以SHY規定最后選出的每個漢字都必須在[l,r]里出現了正偶數次。而且SHY認為選出的漢字的種類數（兩個一樣的漢字稱為同一種）越多越好（為了拿到更多的素材！）。于是SHY請LYD安排選法。 LYD這種傻×當然不會了，于是向你請教…… 問題簡述：N個數，M組詢問，每次問[l,r]中有多少個數出現正偶數次。

Input

輸入第一行三個整數n、c以及m。表示文章字數、漢字的種類數、要選擇M次。 第二行有n個整數，每個數Ai在[1, c]間，代表一個編碼為Ai的漢字。 接下來m行每行兩個整數l和r，設上一個詢問的答案為ans(第一個詢問時ans=0)，令L=(l+ans)mod n+1, R=(r+ans)mod n+1，若L>R，交換L和R，則本次詢問為[L,R]。

Output

輸出共m行，每行一個整數，第i個數表示SHY第i次能選出的漢字的最多種類數。

Sample Input

5 3 5 1 2 2 3 1 0 4 1 2 2 2 2 3 3 5 Sample Output

2 0 0 0 1 Hint

1<=n,c,m<=10^5

比較顯然的分塊題目。不過有許多值得注意的地方，具體自己看代碼。注意，此題卡空間。