Problem : 121 - [Interactive]串珠問題

請在程式碼加入#include "interactive/121.h"回答問題。

　　X教授最近將他的一個最新發明公諸於世，那就是：終極串珠交換機器(Ultimate Bead Swapper，簡稱UBS)。就如同其命名，這個機器會將放置在機器上的一些串珠進行交換，製造出比較特別的串珠列。
　　這個UBS有N個輸送帶，以南北向平行放置。這些輸送帶由左而右依序從1編號到N，每一個輸送帶以相同的速度由北向南輸送。有M個交換器安置在相鄰的輸送帶上，且每個交換器位置和UBS北端的距離皆不相等(換句話說，這些交換器可以根據他們和UBS北端的距離大小排出一個前後順序)，因此可依這些交換器的位置由北而南從1編號到M。圖1顯示從上方看到的UBS 之示意圖。


圖1:具有5個輸送帶及5個交換器的一個終極串珠交換機器(UBS).

　　當使用這個UBS時, N個串珠會被同時擺在各個輸送帶的北端，因此當他們在輸送帶上移動時會排成一條水平線。當兩個串珠移動到一個交換器底下時，該交換器右邊輸送帶上的串珠會移到交換器左邊的輸送帶，左邊輸送帶上的串珠會同時移到右邊的輸送帶。當串珠交換之後，這兩個串珠仍維持和其他串珠排成一條水平線，圖2中顯示一個交換器的運作方式。


圖2: (a)四個串珠在輸送帶上被移動。(b)串珠2及串珠3在經過交換器底下後交換彼此所在的輸送帶。

當給定輸送帶數目N，交換器數目M，以及每個交換器的位置，請你寫一個程式回答以下形式的問題︰
給定一組K及J值，請問起初被放在UBS中編號K的輸送帶北端之串珠，在所有串珠剛通過編號J的交換器後，會位於哪一個編號的輸送帶上?


當讀取以上所描述的輸入資料後，你的程式必須呼叫以下表1中所列的函式，且必須依下述順序呼叫這些函式：
1. 呼叫函式Init，輸送帶數目N (1 ≤ N ≤ 300,000)、交換器數目 M (1 ≤ M ≤ 300,000)，以及各交換器的位置。
2. 呼叫函式getNumQuestions取得Q值(1 ≤ Q ≤ 300,000)，Q值表示接下來要給定的問題數目。
3. 接下來必須執行 Q 次以下指令:
(a)呼叫函式getQuestion 取得一組問題。
(b)呼叫函式answer 來回答所取到該組問題的解答。
我們要特別強調，函式 Init, getNumQuestions 必須先依序被呼叫，且只能被呼叫一次。函式getQuestion及answer必須被交替呼叫:在呼叫函式getQuestion後，你的程式必須先呼叫函式answer後，才能再呼叫getQuestion，反之亦同。若你的程式在執行一組測試資料時違反這個規定，你在該組測試資料將得到0分。

以下為四個函式的使用方法：
1.void Init(int &N,int &M,int x[])：函式會自動為 N,M 賦與該有的值，x為一個長度至少要有 M+1 的陣列，x[1] 到 x[M] 代表分別由北而南的交換器資料，x[i] 代表第 i 個交換器跨越於編號 x[i] 及編號 x[i]+1 的輸送帶上。
2.int getNumQuestions()：回傳你的程式必須回答的問題數目。
3.void getQuestion(int &K, int &J)：K 會被設定成一個輸送帶編號，來指定起初被放在UBS該輸送帶北端之串珠。J 會被設定成所指定交換器的編號。
4.void answer(int x)：對最近一次呼叫getQuestion 讀取到的問題，回答其解答為x。

範例：

詢問	結果
Init(N, M, x);	N=5; M=5; x[1]~x[5]依序為{2,4,1,3,3}(符合圖一的狀況)
getNumQuestions();	回傳2，你有兩個問題需要回答。
getQuestion(K, J);	K=3; J=4。對於起初被放在編號3的輸送帶北端之串珠，在所有串珠剛通過編號4的交換器後，會被交換到哪一個編號的輸送帶?
answer(1);	回答當所有串珠剛通過編號4的交換器後，該串珠會在編號1的輸送帶上。
getQuestion(K, J);	K=5; J=5。對於起初被放在編號5的輸送帶北端之串珠，在所有串珠剛通過編號5的交換器後，會被交換到哪一個編號的輸送帶?
answer(4);	回答當所有串珠剛通過編號5的交換器後，該串珠會在編號4的輸送帶上。

在共20分的測試資料組別中，其M和Q值最大為10,000。