$\TeX$ 是一種由 Donald Knuth 所發展出的一套文書排版軟體。這套軟體可以將原始文件檔加上一些像字型等型態後，轉成一份很漂亮的文件。而一份漂亮的文件是需要用 `` 和 " 來把別人說的話給「引」出來，而不是用大部份鍵盤上有的 "。雖然鍵盤裡通常不會有這種有方向的雙引號鍵，不過上面有左單引號 ` (有人叫 backquote)，和右單引號 ' (有人叫 apostrophe 或 quote)。你可以在你的鍵盤上找一下，不過要小心不要將 ` 與 \ (backslash 鍵) 搞混了。而在 $\TeX$ 裡，使用者可以輸入兩個左單引號 `` 來構成一個左雙引號 ``，或者是兩個右單引號 '' 來構造一個右雙引號 ''，不過呢，通常大家打字時都很習慣用普通的雙引號 " 來引述別人的話。

如果原始文件檔內容是：

"To be or not to be," quoth the bard, "that is the question."

則 TeX 作出來的文件並不會是我們所想要的：

``To be or not to be," quoth the bard, ``that is the question."

為了要得到上面的文件，我們需要把原始文件變成這個樣子：

``To be or not to be,'' quoth the bard, ``that is the question.''

你現在必須要寫一個程式，將普通的雙引號 (")，轉成有方向性的雙引號，而其它文字則不變。而在把普通的雙引號換掉的時候，要特別注意，當要開始引述一句話時要用 ``，而結束引述時要用 ''。不用擔心會有多層巢狀引號的情形，也就是第一個引號一定是用 `` 來代替，再來用 ''，然後用 ``，接著用 ''，依此類推。

Input and Output

輸入是若干列的文字，其中有偶數個雙引號 (")，以 end-of-file 做結束。輸出的文字必須和輸入的一模一樣，除了：

• 每一組雙引號的第一個 " 必須用兩個 ` 字元 (就是 ``) 來代替
• 每一組雙引號的第二個 " 必須用兩個 ' 字元 (就是 '') 來代替。

Sample Input

"To be or not to be," quoth the Bard, "that
is the question".
The programming contestant replied: "I must disagree.
To `C' or not to `C', that is The Question!"

Sample Output

``To be or not to be,'' quoth the Bard, ``that
is the question''.
The programming contestant replied: ``I must disagree.
To `C' or not to `C', that is The Question!''

你即將開車出遠門，當然希望在車上能聆聽一些美好的音樂。你的車上只有播放錄音帶的設備，但是你最喜歡的音樂卻都存放在 CD 上。所以你需要把 CD 上的音樂轉錄到錄音帶上。現在你必須解決的問題是：你的空白錄音帶長共 $N$ 分鐘，你如何選擇 CD 上的歌使得盡可能的利用錄音帶的空間。以下是一些此問題的假設：

• CD 上的歌最多不會超過 20 首。
• 沒有任何一首歌的長度超過 $N$ 分鐘。
• 要錄在錄音帶上的歌不能重複。
• 每首歌的長度以一整數表達。
• $N$ 也是一個整數。

你的程式必須找出該放哪些 CD 上的歌到錄音帶上 (按 CD 上的順序)，使得錄音帶空白的空間最小。

Input

每組測試資料一列，第一個整數為 $N$，代表空白錄音帶的長度。第二個整數 $T$ 代表 CD 上共有多少首歌。接下來的 $T$ 個整數分別代表 CD 上每首歌的長度。以 Sample Input 中第一組測試資料為例說明：$N=5, T=3$, 第一首歌的長度為 1 分鐘，第二首歌的長度為 3 分鐘，第三首歌的長度為 4 分鐘。

Output

對每一組測試資料，輸出一列。內容為要放到錄音帶的各首歌的長度 (注意：此部分答案並非唯一，以第五組測試資料來說，43 2 也是正確的答案。本程式有特殊的檢驗程式，所以只要是正確答案都可被接受)，以及總長度。請參考 Sample Output。

Sample Input

5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2

Sample Output

1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45

很多人都知道銅線是荷蘭人發明的。聽說是有 2 個荷蘭人在爭奪一個銅幣，由於搶的太激烈，銅幣被約拉越長，最後銅線就被發明出來了。

現在，你要來幫助處理一個關於銅幣的問題。給你一袋銅幣 (裡面最多有 100 個，面值可能有 1 分錢到 500 分錢，但單一銅幣是不可分割的)。若要把銅幣分成 2 堆，並且使得這 2 堆銅幣的面值和盡可能接近，你必須回答這 2 堆銅幣面值和的差是多少。

Input

輸入的第一列有一個整數，代表以下有幾組測試資料。

每組測試資料 2 列，其中第一列有 1 個不為負的整數 $m$ ($m\leq{100}$)，代表袋中銅幣的數目。接下來的一列有 $m$ 個正整數，代表袋中各銅幣的面值。

Output

對每一組測試資料，輸出 2 堆銅幣面值和的差是多少。

Sample Input

2
3
2 3 5
4
1 2 4 6

Sample Output

0
1

世界聞名的黑社會老大 Vito Deadstone 要搬到紐約來了。在那裡他有一個大家族，並且他們都住在 Lamafia 大道上。因為 Vito 時常要拜訪所有的親戚，他想要找一間離他們最近的房子，也就是說他希望從他的家到所有的親戚的家的距離的和為最小。

他恐嚇你寫一個程式來幫助幫助他解決這個問題。

Input

輸入的第一列有一個整數代表以下有多少組測試資料。

每組測試資料一列，第一個整數 $r$ ($0 < r < 500$)，代表他親戚的數目。接下來的 $r$ 個整數 $s_1,s_2,\cdots,s_i,\cdots,s_r$ 為這些親戚房子的門牌號碼 ($0 < s_i <30000$)。注意：有些親戚的門牌號碼會相同。

Output

對每一組測試資料，輸出從他的新家到所有的親戚的家的距離的和為最小為多少。2 個門牌號碼 $s_i$、$s_j$ 的距離為 $s_i-s_j$ 的絕對值。

Sample Input

3
2 2 4
3 2 4 6
4 2 1 999 5

Sample Output

2
4
1001

從前從前在古帝國有 2 座高塔位於 2 座城市中，他們的形狀不太相同。但是他們都是用圓柱形的石塊一個堆在另一個上面建起來的。每個圓柱形石塊的高度都相同 (定為 1)，但是半徑卻不一。所以，雖然 2 座高塔的形狀不一樣，但事實上他們可能有許多石塊是相同的。

在高塔建成的一千年後，國王要求建築師拿掉高塔的某些石塊，使得 2 座高塔的形狀大小和高度一樣。但同時要盡可能讓高塔的高度越高越好。新高塔的石塊的順序也必須和原來的高塔一樣。國王認為這樣可以代表 2 座城市之間的和諧與平等。他為這 2 座高塔命名為「雙子星塔」。

現在，你的任務是就是算出這雙子星塔的高度。

Input

輸入含有多組測試資料，每組測試資料 3 列，代表原來 2 座高塔的資料。

每組測試資料的第一列有 2 個整數 $N_1$ 和 $N_2$ ($1\leq{N_1,N_2}\leq{100}$)，代表這 2 座高塔原來的高度。接下來的一列有 $N_1$ 個正整數，代表第一座高塔石塊的半徑 (由高到低)。再接下來的一列有 $N_2$ 個正整數，代表第二座高塔石塊的半徑 (由高到低)。

$N_1=0, N_2=0$ 代表輸入結束。

Output

對每一組測試資料，輸出這是第幾組測試資料以及這2座塔後來的高度。每組測試資料後請空一列。請參考 Sample Output。

Sample Input

7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
0 0

Sample Output

Twin Towers #1
Number of Tiles : 4

Twin Towers #2
Number of Tiles : 6