Because of the thriller adventure game _The 3rd Building_, more and more students get interested in workshops. Because of this, Kanade found that when the recruitment just started, many more students participated this year than before. But Kanade hates recruitment. She is annoyed by preparing recruitment questions. It's time for her to set a question, but she has no idea.
One day, she came up with an idea. Given $n$ binary strings, i.e., strings only consist of _0_ and _1_. Now she'd like to choose $textbf(o n e)$ binary string among them, then spilt it into two non-empty binary strings. Formally, for binary string $s_i$ whose length is $l " "(l >= 2)$, she will choose an integer $k in [ 1, l -1 ]$ at first. Then let the prefix of $s_i$ of length $k$ be a new binary string $s_{n + 1}$. Finally, delete that prefix from string $s_i$. After this operation, the length of $s_i$ becomes $l -k$, and there are $n + 1$ binary strings.
Kanade wants to know the number of different operations which can make the exclusive-or of the $n + 1$ binary strings *only contains* _0_. Two operations consider different if the binary strings which are chosen to split are different, or the values of $k$ are different.
Let $a$ be a binary string whose length is $n$, $b$ be a binary string whose length is $m$. Let $c$ be the exclusive-or of $a$ and $b$, denoted $a plus.circle b$, then $c$ is a binary string of length $max {n, m}$, which is defined as
$$ c_i= (a \oplus b)_i = \begin{cases} \texttt{1}, & (1\le i\le \min\{n,m\},a_i\neq b_i)\\ \texttt{0}, & (1\le i\le\min\{n,m\},a_i= b_i)\\ a_i, & (i>\min\{n,m\},n>m)\\ b_i, & (i>\min\{n,m\},n<m) \end{cases} $$
The exclusive-or of $n + 1$ strings $s_1, s_2, \\\\cdots, s_n, s_(n + 1)$ is thus defined as $s_1 plus.circle s_2 plus.circle \\\\cdots plus.circle s_n plus.circle s_(n + 1)$.
Note that a binary string is a string where each character is indexed from left to right. This is different from the binary form of an integer.
She thought it easy to solve, but few students managed this question. She wants to know if her standard program was wrong. Please write a program solving the question above, so that she can check her code.
The first line contains an integer $n " "(1 <= n <= 10^5)$ — the number of binary strings.
In the next $n$ lines, each line contains a binary string $s_i " "(1 <= | s_i | <= 10^6)$, where $| s_i |$ denotes the length of $s_i$. The sum of all binary strings' lengths will not exceed $10^6$.
It is guaranteed that there exists a binary string whose length is greater than $1$.
Output one integer in a line, representing the answer.
## Input
The first line contains an integer $n " "(1 <= n <= 10^5)$ — the number of binary strings.In the next $n$ lines, each line contains a binary string $s_i " "(1 <= | s_i | <= 10^6)$, where $| s_i |$ denotes the length of $s_i$. The sum of all binary strings' lengths will not exceed $10^6$.It is guaranteed that there exists a binary string whose length is greater than $1$.
## Output
Output one integer in a line, representing the answer.
[samples]
**Definitions**
Let $ k = n \times m + 1 $ with $ 2 \leq n \leq m \leq 100 $.
Let $ A = \{a_1, a_2, \dots, a_k\} $ be a set of $ k $ distinct integers, exactly $ k-1 $ of which form an $ n \times m $ grid $ G $ such that:
- The grid $ G $ satisfies $ G_{i,j} = (i-1) \cdot m + j - 1 $ for all $ i \in \{1, \dots, n\}, j \in \{1, \dots, m\} $,
- The missing value $ x \in A $ is the *extra piece* (password), and $ A \setminus \{x\} $ forms $ G $.
**Constraints**
1. $ 2 \leq n \leq m \leq 100 $, so $ 5 \leq k \leq 10001 $.
2. All $ a_i \in [0, 10^9] $, distinct.
3. At most $ 2k $ queries of type $ r\ x\ y $ or $ c\ x\ y $ are allowed.
4. Only one $ !\ x $ query is allowed, after which the program must terminate.
**Objective**
Identify the unique $ x \in A $ such that $ A \setminus \{x\} $ can be arranged into an $ n \times m $ grid where cell $ (i,j) $ contains value $ (i-1) \cdot m + j - 1 $.
**Query Types**
- $ r\ x\ y $: Query whether the row containing $ x $ also contains $ y $ in the correct grid $ G $.
- $ c\ x\ y $: Query whether the column containing $ x $ also contains $ y $ in the correct grid $ G $.
- $ !\ x $: Output $ x $ as the password and terminate.