電位計 (potentiometer,簡稱 potmeter) 是一種有可變電阻的電子設備,它有兩個接點 (terminal) 和一些控制結構 (通常是刻度盤、齒輪或者滑塊) 使得我們可以調整兩接點間的電阻值從 0 (無電阻) 到一個最大值。電阻的單位是歐姆 (Ohm),當有兩個以上的電阻串聯 (也就是一個接著一個連接) 在一起,總電阻就會是個別電阻的總和。
在這個問題中,我們考慮 $N$ 個串聯的電位計,從左到右分別編號為 1 號到 $N$ 號,第 $x$ 號的電位計左側接點和第 $x-1$ 號的右側相連,且第 $x$ 號的電位計右側接點和第 $x+1$ 號的左側相連,而 1 號電位計的左側接點和 $N$ 號的右側接點並沒有接上其他東西。
一開始所有電位計會有介於 0 到 1000 歐姆的電阻,我們可以做兩件事:
- 設定其中一個電位計為另一個電阻值
- 測量任意兩個接點之間的電阻
Input
輸入有不超過 3 組測資。每組測資一開始有一個 $N$,代表電位計的數量,$N$ 可以大到 200000。接著有 $N$ 行,每行有一個介於 0 到 1000 的數字,代表 1 號到 $N$ 號電位計的初始電阻值。接著有數次操作,每行代表一個操作,操作數可達到 200000 次,這裡有 3 種操作:
- 「S $x$ $r$」- 設定第 $x$ 號電位計的電阻值為 $r$ 歐姆,$x$ 會是一個有效的電位計編號而 $r$ 介於 0 到 1000
- 「M $x$ $y$」- 測量 $x$ 號左側接點到 $y$ 號右側接點的電阻,兩個編號都會是有效的且 $x$ 小於等於 $y$
- 「END」- 該筆測試資料的結束,只會在一系列操作的最尾端出現一次
如果一筆 $N=0$ 的測資出現代表輸入結束,並且此筆測資不需處理。
Output
對於輸入的每筆測資,請先生出一行「Case n:
」,而 $n$ 是從 1 開始的測資編號。
而對於輸入中每次的測量操作,輸出包含一個數字的一行,此數字為測量到電阻值。這些操作會作用在依照輸入順序的電位計中。
請在每組測資間輸出一個空白行。
注意: 輸入測資非常大 (~ 8 MB) 所以要用快一點的 IO 方法。
Sample Input
3
100
100
100
M 1 1
M 1 3
S 2 200
M 1 2
S 3 0
M 2 3
END
10
1
2
3
4
5
6
7
8
9
10
M 1 10
END
0
Sample Output
Case 1:
100
300
300
200
Case 2:
55