你知道四千很喜歡玩Rabi-Ribi。這是個愛冒險的主角Erina，儘管被人們所憎恨，仍然深愛著這個世界的熱血遊戲。
這款遊戲最具特色也最有趣的地方便是boss戰裡的各種彈幕攻擊了。一隻boss擁有$M$種彈幕，在血量降為$0$前不斷選出一種彈幕攻擊Erina。四千雖然知道每種彈幕的躲法，常常卻因為無法及時判斷這是哪種彈幕而讓Erina受傷。有天四千發現，一隻boss的出招順序只跟她的前$K$次攻擊中選擇的彈幕有關。將boss的彈幕編號為$0, 1, \ldots, M-1$，並假設她在第$i (1 \leq i \leq K)$次攻擊選擇了彈幕$a_i$，則第$N$次的攻擊招式由下方的C函式給出：
long long ChooseAttack(long long N){
if(N <= K){
return a[N];
}else{
long long sum = 0;
for(long long i=1; i<=K; i++){
sum = sum + c[i]*ChooseAttack(N-i);
}
return sum % M;
}
}
其中$\{c_i\}_{i=1}^K$是個全域long long陣列。不幸的是，四千發現他的C compiler壞了，因為不管等了多久，他的C程式都沒辦法算出ChooseAttack(100000)的值。現在他給你$M, K, N, \{a_i\}_{i=1}^K, \{c_i\}_{i=1}^K$，請你用ZJ的compiler幫他算出ChooseAttack(N)的值。
本題的輸入有$T$筆測資，請讀至檔案尾。
每筆測試資料佔三行。
第一行有三個正整數$M, K, N$，代表意義如上所述。
第二行有$K$個非負整數$a_1, a_2, \ldots, a_K$，代表這隻boss前$K$次彈幕攻擊的編號。
第三行有$K$個非負整數$c_1, c_2, \ldots, c_K$，代表函式ChooseAttack()中出現的神秘陣列。
每一行的所有整數皆由一個空白隔開，且行末沒有多餘空白。
- $1 \leq T \leq 10$
- $1 \leq M \leq 10^7$
- $1 \leq K \leq 20000$，且若$T \geq 2$，保證所有的$K \leq 100$
- $1 \leq N \leq 10^9$
- $0 \leq a_i \leq M-1$
- $0 \leq c_i \leq M-1$
對於每筆測試資料，輸出一個介於$0$與$M-1$之間的整數$A$，代表這隻boss在第$N$次攻擊選擇的彈幕編號，亦即ChooseAttack(N)的值，佔一行。
10 2 8 0 1 1 1 5 5 100000 0 1 2 3 4 0 0 0 0 1
3 4
不公開 測資點#0 (10%): 5.0s , <1M
不公開 測資點#1 (10%): 5.0s , <1M
不公開 測資點#2 (10%): 5.0s , <1M
不公開 測資點#3 (10%): 5.0s , <1M
不公開 測資點#4 (10%): 5.0s , <1M
不公開 測資點#5 (10%): 5.0s , <1M
不公開 測資點#6 (10%): 5.0s , <1M
不公開 測資點#7 (10%): 5.0s , <1M
不公開 測資點#8 (10%): 5.0s , <1M
不公開 測資點#9 (10%): 5.0s , <1M
- 第一筆測資中，boss在第$N$次攻擊放的彈幕編號恰為費氏數列第$N-1$項的個位數，故$A=3$。
第二筆測資中，不難觀察到boss放彈幕的順序為$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, \ldots$，故$A=4$。 - 那張圖片中的攻擊雖然看起來很可怕，其實只要站著不動就不會被打到。
- 如果你對那張圖片中的boss戰有興趣，可以看看這個。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 13272 | xavier13540 (柊 四千) | c490 | 1038 | 2018-01-22 23:42 |