鐵沙掌
- 卦長是最近在練習鐵砂掌(參閱鐵沙掌)。現在有許多的磚頭再卦長面前排成一排，每個磚頭都有其破碎值，只要施加的能量大於等於破碎值磚頭就會破掉，同時也會消耗掉與破碎值大小相等的能量。卦長想從特定的區段挑選出盡量多的磚頭來打碎，這些磚頭的破碎值總和不能超過他手的能量值，請問他最多可以打碎幾塊磚頭呢?
- 卦長已經知道答案了，但是為了謹慎起見他還是希望請你幫他寫一個程式來確認他的答案是否正確，但為了肉眼比對方便，卦長決定比較結果的雜湊值就好，也就是假設對每次詢問所能打破的磚頭數依序為$p_1,p_2,...,p_k$，則我們定義其雜湊值為$(p_1+1) \oplus (p_2+2) \oplus ··· \oplus (p_k+k)$，其中$\oplus$代表xor運算。
輸入說明:
- 輸入檔的第一行有一個正整數$T \; (T \leq 514)$，表示接下來總共有幾筆測試資料。
- 每一筆測試資料第一行有兩個正整數$N,Q \;(N,Q \leq 10^5)$，代表總共有$N$塊磚頭，卦長將問你$Q$個問題。磚頭編號由左到右為$1,2,...,N$。下一行有$N$個非負整數，依序代表塊磚頭的破裂值，破裂值不會超過$10^4$。再接下來有$Q$行，每行有三個整數$L,R,S \; (1 \leq L \leq R \leq N, \; 0 \leq S \leq 10^9)$，代表卦長想問你如果他的手的能量值為$S$，他最多可以打破幾塊編號在$L$到$R$ 之間的磚頭呢？
輸出說明
範例輸入:
2
3 1
5 1 4
1 3 5
5 2
1 1 5 1 5
2 5 5
1 4 5
範例輸出:
3
6
配分:
| 配分 |
限制 |
| 100% |
與題目相同 |
| 時限 |
350ms |
| 記憶體 |
5120000 kb |
Judge Setting
run-time limit: 350 ms
memory limit: 5120000 byte
測資數量: 0