301 . SOS

Description

SOS（摩斯電碼：···---···）是目前國際通用的摩斯電碼求救訊號。 第一次作為一種標準被採用是在1905年4月1日由德國政府規定的關於無線電的管理條例中，並於1906年11月3日成為國際標準（之前國際常用CQD求救訊號，但並未成為標準）。在1908年7月1日後被廣泛採用。

之所以制訂新遇難訊號為SOS，是因為當時的抗干擾技術很差，之前常用的CQD訊號，由於傳送碼長，而且電碼的符號不一致，而S與O是摩斯電碼中少有的連續碼而且對操作員來說較易使用。而SOS在之後也成為一個易記、實用的求救方式。

有記錄的首次使用SOS求救訊號的時間是在1909年8月11日，當時汽船阿拉帕霍號（S.S. Arapahoe）駛至北卡羅來納州的哈特拉斯角後燃油殆盡，發出救援36小時後被救[1]。

其中一次較知名的利用SOS求救訊號就是在1912年4月14日晚上英國郵輪鐵達尼號將在北大西洋沉沒時。當時英國人多數是利用CQD求救訊號，不過當晚也用了新的SOS求救訊號，希望有郵輪來拯救他們。不過該求救訊號直到第二天早上才被加州人號收到，因為加州人號的電報員關了電報機下班睡覺去了。而鐵達尼號的無線電首席官員傑克·菲利普起初一直在發送傳統的CQD遇難訊號，直到下級無線電操作員哈羅德·布萊德建議他：「發送SOS吧，這是新的呼叫訊號，這也可能是你最後的機會來發送它了！」然後菲利普才在傳統的CQD求救訊號中夾雜SOS訊號。

由於現代無線電通訊技術的發展，船舶與航空器越來越少使用摩斯電碼通訊，因此除了業餘無線電外，SOS已逐漸停用，改以國際海事衛星電子通信裝置的全球海上遇險及安全系統（GMDSS）代替。

-出自維基百科

以上是 SOS 的介紹，但是跟本題沒有任何關聯。

有一個神奇的函數 $f$$f$，定義域是 $0$$0$ 到 $n-1$$n-1$ 的整數。 對於一個非負整數 $x$$x$，定義

其中對於一個多重集合 $S$$S$，$\underset{x\in S}{⨁}S$$\bigoplus_{x \in S} S$ 代表所有數字的位元異或 (xor) 和。 $a_x$$a_x$ 是一個給定的數值，$xANDy$$x \ AND \ y$ 代表 $x$$x$ 跟 $y$$y$ 兩個數字的位元 AND。輸出 $f(n-1)$$f(n-1)$ 模 $2^{30}$$2^{30}$ 的數值。

Input Format

第一行有一個數字 $n$$n$ 第二行有 $n$$n$ 個數字 $a_0,a_1,\cdots ,a_{n-1}$$a_0, a_1, \cdots, a_{n-1}$ 保證 $1\le n\le 2^{20},0\le a_i<2^{30}$$1 \leq n \leq 2 ^ {20}, 0 \leq a_i < 2^ {30}$

Output Format

輸出一行，為 $f(n-1)$$f(n-1)$ 模 $2^{30}$$2^{30}$ 的數值。

Sample Input 1

4
2 1 3 2

Sample Output 1

xxxxxxxxxx
12

Subtasks

Testdata and Limits