檔案傳輸程式通常都會估計並顯示剩餘的傳輸時間，用來估計剩餘時間的原則為：將剩餘欲傳送的資料大小 (bytes) 除以前幾秒的平均傳輸率。本題請你寫程式模擬這個功能。

Input

輸入會有多組測試資料，每組資料表示一次的檔案傳輸。每組資料的第一列為一個非零的整數表示檔案的大小 (bytes)，接下來的每一列依序為每一秒所傳輸的資料量 (bytes)，傳輸的總資料量會等於檔案的大小。

當檔案大小等於 0 時表示測試資料結束。

Output

每組輸出資料的第一列請輸出該組資料編號及檔案的大小，接下來每 5 秒輸出一次剩餘檔案傳輸所需的秒數。

計算所需的秒數時請先計算前五秒的平均傳輸率 (bytes/秒)，若這 5 秒沒有傳輸任何資料表示這次的傳輸為 stalled，你的程式必須輸出這種情況，否則請將剩餘資料量除以前 5 秒的平均傳輸率，得到剩餘秒數。剩餘秒數必須為整數，請無條件進位到整數 (例如 12.2 進位到 13)。

請在每組輸出資料的最後輸出該次傳輸共耗時多少秒，其格式請參考範例資料。

每組輸出之後請額外輸出一列空行。

Sample Input

100
10
20
20
0
10
0
10
0
10
0
20
200
60
30
100
10
50
5
5
5
5
25
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0

Sample Output

Output for data set 1, 100 bytes:
   Time remaining: 4 seconds
   Time remaining: 5 seconds
Total time: 11 seconds

Output for data set 2, 200 bytes:
Total time: 4 seconds

Output for data set 3, 50 bytes:
   Time remaining: 1 seconds
   Time remaining: stalled
   Time remaining: stalled
   Time remaining: 0 seconds
Total time: 20 seconds
　

為了舉辦「國際ACM世界學校競賽」，市長決定為每所學校提供穩定可靠的電力，為了達成這個目標，其中某一所學校的電力系統必須與發電廠直接連接，且部份學校間的電力系統亦需互相連接。

用來評估一所學校的電力是否穩定的原則為：

1. 若某學校的電力系統與發電廠直接相連，則該學校的電力是穩定的，
2. 或某學校與另一所電力穩定的學校直接相連，則該學校的電力也是穩定的。

給定學校間彼此連線的成本，市長必須決定兩種可能的連線路線使得成本最小。成本 的計算為學校間的連線成本總和。請你幫市長找出兩種最便宜的連線路徑。

Input

輸入的一開始有一個整數 T ($1\leq{T}\leq{15}$) 表示測試資料的組數，接下有來 T 組測試資料，每組資料的一開始有兩個以空白字元隔開的整數 N、M，N ($3\leq{N}\leq{100}$) 表示學校的總數，M 表示學校間可能的連線數，接下來有 M 組連線，每組有三個整數 $A_i, B_i, C_i$，$C_i$ ($1\leq{C_i}\leq{300}$) 表示 $A_i$ 與 $B_i$ 兩所學校的連線成本。學校的編號為 1 到 N。

Output

每組測試資料輸出一列，每列有兩個以空白字元隔開的整數 $S_1, S_2$，分別表示最低連線成本與次低連線成本，$S_1\leq{S_2}$。你可以假設 $S_1, S_2$ 必存在。

Sample Input

2
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
9 14
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10

Sample Output

110 121
37 37

Luchu Bandor 是一隻猴子，他想找交住的對象，所以他到「猴子女子學校」挑對象，他挑選對象的原則是：希望找到所有比他矮的猴子中最高的，或是所有比他高的猴子中最矮的。早上猴子女子學校的母猴子們會由矮到高依序排成一列 (非遞減的順序)。請你幫他選擇其中兩個可能的人選。

Input

輸入只會有一組測試資料，第一列給定一個整數 N ($1\leq{N}\leq{50000}$) 表示母猴的數目，下一列會有 N 個整數，其值介於 $1 \sim 2^{31}-1$ 之間，分別表示 N 隻母猴的身高，每個整數之間會以一個空白字元隔開，且以非遞減的順序列出。下一列有一個整數 Q ($1\leq{Q}\leq{25000}$) 表示欲查詢的次數，每個查詢會給定 Luchu Bandor 的身高，即接下來會有 Q 個整數，其值介於 $1 \sim 2^{31}-1$ 之間，並以一個空白字元隔開。注意，Q 個整數並非以遞增或遞減的方式列出。

Output

針對每次查詢，請在一列輸出兩個整數，並以一個空白字元隔開，第一個整數表示較矮的猴子中最高的高度，第二個數數表示較高的猴子中最矮的高度，若不存在請輸出 X。

Sample Input

4
1 4 5 7
4
4 6 8 10

Output for Sample Input

1 5
5 7
7 X
7 X

註：請至少用 scanf() 和 printf() 來對這個問題輸入和輸出，cin 和 cout 對這問題的時間限制來說太慢了。很抱歉我們無法調整時間限制。

有一個國家叫「方塊國」，方塊國使用「方塊幣」當作流通的貨幣，這種貨幣是由方塊所組成，其面額是 1 ~ 21 的立方倍，也就是 $1,8,27,\cdots{},9261$。

你的任務是要計算用方塊幣付款的所有可能方式，例如付 21 元共有三種付款方式：

1. 付 21 個 1 元方塊幣
2. 付 1 個 8 元方塊幣加 13 個 1 元方塊幣
3. 付 2 個 8 元方塊幣加 5 個一元方塊幣。

輸入的每一列會有一個整數，請你計算此金額的所有可能付款方式，此金額大小介於 1 ~ 10000 之間。

Sample input

10 
21
77
9999

Output for sample input

2
3
22
440022018293

本問題請你轉換一字串使之變成迴文字串 (一種從前面寫與從後面寫都一樣的字串，例如 abcba)，藉由新增、刪除、取代字母等步驟來轉換成迴文字串，並使轉換的步驟最小化。更精確地說，你可以執行的步驟有三種：

• 新增：插入一字母到字串中任一位置。
• 刪除：刪除字串中任一字母。
• 取代：以一個字母取代字串中任一字母。

每執行上述三種步驟中的任一種即算一次，你必需使轉換步驟愈少愈好。

例如字串 abccda，如果只允許以新增字母的方式轉換字串，則最少需要兩個步驟，若允許以取代的方式轉換字串，則最少僅需一個步驟。當然，本問題是允許你三種步驟都能使用。

Input

輸入的第一列有一個整數 $T$ ($1\leq{T}\leq{10}$) 表示接下來有 $T$ 列測試資料，每列測試資料皆為一個僅含小寫字母的字串，字串長度不會超過 1000 個字元。

Output

請對每組測試資料輸出其編號，與使字串變成迴文字串的最少步驟為何。

Sample Input

6
tanbirahmed
shahriarmanzoor
monirulhasan
syedmonowarhossain
sadrulhabibchowdhury
mohammadsajjadhossain

Output for Sample Input

Case 1: 5
Case 2: 7
Case 3: 6
Case 4: 8
Case 5: 8
Case 6: 8

在某個小鎮上流行著一種遊戲，遊戲中每一隊的隊員數目一定是奇數，且人數最少一位、最多不超過 10 位，而隊員的年紀必須介於 11 ~ 20 歲，且不會有任兩位隊員的年紀相同。每一隊都有一個隊長，由於年紀差異的關係，隊員與隊員之間的溝通多少會有代溝，年紀差異愈大代溝就愈大，為此，他們選擇隊長的原則是：年紀比隊長大的人數會等於年紀比隊長小的人數。

本題會給你所有隊員的年紀，請你找出隊長的年紀為何。

Input

輸入一開始會有一個表示測試資料組數的整數 $T$ ($T\leq{100}$)。

接下來會有 $T$ 列，每列代表一組測試資料，每組測試資料的第一個整數 $N$ ($1 < N < 11$) 表示隊員的總數。接下來會有 $N$ 個以空白字元隔開的整數代表每位隊員的年紀，年紀介於 11 ~ 20 歲之間，此 $N$ 個數必定是以嚴格遞增或嚴格遞減的順序排列。

Output

請輸出資料格式 Case x: a，x 表示測試資料的編號，a 表示隊長的年紀。

Sample Input

2
5 19 17 16 14 12
5 12 14 16 17 18

Sample Output

Case 1: 16
Case 2: 16

給定一元二次方程式 $f(x)=ax^2+bx+c$，及除數 d 與最大值 L，請計算共有多少個函數值 f(0), f(1), …,f(L) 可整除於 d。

Input

輸入包含多組測試資料，每組測試資料一列，每列有五個整數 a b c d L ($-1000\leq{a, b, c}\leq{1000}$, $1 < d < 1000000$, $0\leq{L} < 1000$)。以 0 0 0 0 0 表示資料結束。

Output

請在每列輸出每組測試資料的答案 (共有多少個函數值 f(0), f(1), …, f(L) 能整除於 d)。

Sample Input

0 0 10 5 100
0 0 10 6 100
1 2 3 4 5
1 2 3 3 5
0 0 0 0 0

Sample Output

101
0
0
4

有一個工頭與一群伐木工，工頭很喜歡找伐木工們的麻煩，他會要求伐木工們以十個一組按照他們的鬍子長短依序排成一列。

你請寫一個程式判斷伐木工是否以由長到短，或以由短到長的順序排成一列。不會有人的鬍子一樣長。

Input

第一列有一個整數 $N$ ($0 < N < 20$) 表示測試資料的組數，接下來有 $N$ 列，每列有 $10$ 個相異的正整數表示每人鬍子的長短。

Output

請以 Ordered 表示有照順序排列，以 Unordered 表示沒有照順序排列，第一列請輸出 Lumberjacks:。

Sample Input

3
13 25 39 40 55 62 68 77 88 95
88 62 77 20 40 10 99 56 45 36
91 78 61 59 54 49 43 33 26 18

Sample Output

Lumberjacks:
Ordered
Unordered
Ordered