Circular Key Feature

A key is a string of length \(n = 2k+1\) consisting of exactly 1 symbol \(X\), \(k\) letters \(A\) and \(k\) letters \(B\). For example, when \(k=3\), BAXABAB is a valid key.

The \(2k+1\) letters are arranged on a circle with positions numbered \(1,2,\dots,2k+1\) in clockwise order. Suppose that the positions of \(k\) letters \(A\) are fixed (or, in another version, the positions of \(k\) letters \(B\) are fixed) and the remaining positions will be filled by the other letter (either \(B\) or \(A\)) except one position that will be occupied by \(X\). It can be proven that the \(k+1\) keys that can be formed (by choosing a position for \(X\) among the free slots) have distinct feature values, which are exactly \(0,1,2,\dots,k\).

The feature value of a key is defined as the number of "strong" \(A\)'s. When reading clockwise starting from the position of \(X\), consider the sequence of the remaining \(2k\) letters. Let \(d_i\) be the difference between the number of \(A\)'s and \(B\)'s encountered in the first \(i\) letters. An \(A\) is called strong if, at the moment it is encountered, \(d_i > 0\).

Your task is to solve the following three queries:

1. Given the positions of all \(A\)'s, if the feature value is \(0\), determine the position of \(X\).
2. Given the positions of all \(A\)'s and a specified feature value \(S\) (with \(0 \le S \le k\)), determine the position of \(X\).
3. Given the positions of all \(B\)'s and a specified feature value \(S\) (with \(0 \le S \le k\)), determine the position of \(X\).

Note: The positions are numbered from \(1\) to \(2k+1\). It is guaranteed that for each setting, the \(k+1\) possible positions for \(X\) yield feature values that are exactly \(0,1,2,\dots,k\) in some order.

Example 1:

• For \(k=3\) and \(S=2\):
  • When the positions of \(A\)'s are {2, 4, 6} and the feature value is \(0\), the answer is 7.
  • When the positions of \(A\)'s are {2, 4, 6} and the feature value is \(2\), the answer is 3.
  • When the positions of \(B\)'s are {2, 4, 6} and the feature value is \(2\), the answer is 5.

Example 2:

• For \(k=9\) and \(S=7\):
  • When the positions of \(A\)'s are {3, 4, 5, 9, 10, 12, 13, 16, 19} and the feature value is \(0\), the answer is 14.
  • When the positions of \(A\)'s are {3, 4, 5, 9, 10, 12, 13, 16, 19} and the feature value is \(7\), the answer is 18.
  • When the positions of \(B\)'s are {3, 4, 5, 9, 10, 12, 13, 16, 19} and the feature value is \(7\), the answer is 17.

Input Format:

The input begins with a line containing integers separated by spaces. The format is as follows:

• If solving query type 1: The first line contains 1 and \(k\). Then the next line contains \(k\) distinct integers representing the positions of letter \(A\).
• If solving query type 2: The first line contains 2, \(k\) and \(S\). Then the next line contains \(k\) distinct integers representing the positions of letter \(A\).
• If solving query type 3: The first line contains 3, \(k\) and \(S\). Then the next line contains \(k\) distinct integers representing the positions of letter \(B\).

Output Format:

Output the position of \(X\) that yields the specified feature value.

inputFormat

The input consists of two lines.

On the first line, depending on the query:

• For query type 1: 1 k
• For query type 2: 2 k S
• For query type 3: 3 k S

The second line contains \(k\) space-separated integers indicating the positions of the fixed letter (\(A\) for query types 1 and 2, \(B\) for query type 3).

It is guaranteed that \(0 \le S \le k\) (for query types 2 and 3) and positions are in the range \(1\) to \(2k+1\).

outputFormat

Output a single integer representing the position of \(X\) that results in the key having the given feature value.

sample

1 3
2 4 6

7