1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Minimize!
Contest: Codeforces Round 971 (Div. 4)
Difficulty rating: 800
Tags: brute force, math

You are given two integers $$$a$$$ and $$$b$$$ ($$$a \leq b$$$). Over all possible integer values of $$$c$$$ ($$$a \leq c \leq b$$$), find the minimum value of $$$(c - a) + (b - c)$$$.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 55$$$) — the number of test cases.

Each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a \leq b \leq 10$$$).

Output format:
For each test case, output the minimum possible value of $$$(c - a) + (b - c)$$$ on a new line.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can choose $$$c = 1$$$ and obtain an answer of $$$(1 - 1) + (2 - 1) = 1$$$. It can be shown this is the minimum value possible.

In the second test case, you can choose $$$c = 6$$$ and obtain an answer of $$$(6 - 3) + (10 - 6) = 7$$$. It can be shown this is the minimum value possible.

Example input:
3
1 2
3 10
5 5

Example output:
1
7
0

Editorial:
osu!mania
Contest: Codeforces Round 971 (Div. 4)
Difficulty rating: 800
Tags: brute force, implementation

You are playing your favorite rhythm game, osu!mania. The layout of your beatmap consists of $$$n$$$ rows and $$$4$$$ columns. Because notes at the bottom are closer, you will process the bottommost row first and the topmost row last. Each row will contain exactly one note, represented as a '#'.

For each note $$$1, 2, \dots, n$$$, in the order of processing, output the column in which the note appears.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

For each test case, the first line contains $$$n$$$ ($$$1 \leq n \leq 500$$$) — the number of rows of the beatmap.

The following $$$n$$$ lines contain $$$4$$$ characters. The $$$i$$$-th line represents the $$$i$$$-th row of the beatmap from the top. It is guaranteed that the characters are either '.' or '#', and exactly one of the characters is '#'.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$.

Output format:
For each test case, output $$$n$$$ integers on a new line, the column that the $$$i$$$-th note appears in for all $$$i$$$ from $$$1$$$ to $$$n$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
3
4
#...
.#..
..#.
...#
2
.#..
.#..
1
...#

Example output:
4 3 2 1 
2 2 
4

Editorial:
The Legend of Freya the Frog
Contest: Codeforces Round 971 (Div. 4)
Difficulty rating: 1100
Tags: implementation, math

Freya the Frog is traveling on the 2D coordinate plane. She is currently at point $$$(0,0)$$$ and wants to go to point $$$(x,y)$$$. In one move, she chooses an integer $$$d$$$ such that $$$0 \leq d \leq k$$$ and jumps $$$d$$$ spots forward in the direction she is facing.

Initially, she is facing the positive $$$x$$$ direction. After every move, she will alternate between facing the positive $$$x$$$ direction and the positive $$$y$$$ direction (i.e., she will face the positive $$$y$$$ direction on her second move, the positive $$$x$$$ direction on her third move, and so on).

What is the minimum amount of moves she must perform to land on point $$$(x,y)$$$?

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

Each test case contains three integers $$$x$$$, $$$y$$$, and $$$k$$$ ($$$0 \leq x, y \leq 10^9, 1 \leq k \leq 10^9$$$).

Output format:
For each test case, output the number of jumps Freya needs to make on a new line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, one optimal set of moves is if Freya jumps in the following way: ($$$0,0$$$) $$$\rightarrow$$$ ($$$2,0$$$) $$$\rightarrow$$$ ($$$2,2$$$) $$$\rightarrow$$$ ($$$3,2$$$) $$$\rightarrow$$$ ($$$3,5$$$) $$$\rightarrow$$$ ($$$6,5$$$) $$$\rightarrow$$$ ($$$6,8$$$) $$$\rightarrow$$$ ($$$9,8$$$) $$$\rightarrow$$$ ($$$9,11$$$). This takes 8 jumps.

Example input:
3
9 11 3
0 10 8
1000000 100000 10

Example output:
8
4
199999

Editorial:
Satyam and Counting
Contest: Codeforces Round 971 (Div. 4)
Difficulty rating: 1400
Tags: geometry, math

Satyam is given $$$n$$$ distinct points on the 2D coordinate plane. It is guaranteed that $$$0 \leq y_i \leq 1$$$ for all given points $$$(x_i, y_i)$$$. How many different nondegenerate right triangles$$$^{\text{∗}}$$$ can be formed from choosing three different points as its vertices?

Two triangles $$$a$$$ and $$$b$$$ are different if there is a point $$$v$$$ such that $$$v$$$ is a vertex of $$$a$$$ but not a vertex of $$$b$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — the number of points.

The following $$$n$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \leq x_i \leq n$$$, $$$0 \leq y_i \leq 1$$$) — the $$$i$$$'th point that Satyam can choose from. It is guaranteed that all $$$(x_i, y_i)$$$ are pairwise distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
Output an integer for each test case, the number of distinct nondegenerate right triangles that can be formed from choosing three points.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The four triangles in question for the first test case:

Example input:
3
5
1 0
1 1
3 0
5 0
2 1
3
0 0
1 0
3 0
9
1 0
2 0
3 0
4 0
5 0
2 1
7 1
8 1
9 1

Example output:
4
0
8

Editorial:
Klee's SUPER DUPER LARGE Array!!!
Contest: Codeforces Round 971 (Div. 4)
Difficulty rating: 1400
Tags: binary search, math, ternary search

Klee has an array $$$a$$$ of length $$$n$$$ containing integers $$$[k, k+1, ..., k+n-1]$$$ in that order. Klee wants to choose an index $$$i$$$ ($$$1 \leq i \leq n$$$) such that $$$x = |a_1 + a_2 + \dots + a_i - a_{i+1} - \dots - a_n|$$$ is minimized. Note that for an arbitrary integer $$$z$$$, $$$|z|$$$ represents the absolute value of $$$z$$$.

Output the minimum possible value of $$$x$$$.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

Each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n, k \leq 10^9$$$) — the length of the array and the starting element of the array.

Output format:
For each test case, output the minimum value of $$$x$$$ on a new line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, $$$a = [2, 3]$$$. When $$$i = 1$$$ is chosen, $$$x = |2-3| = 1$$$. It can be shown this is the minimum possible value of $$$x$$$.

In the third sample, $$$a = [3, 4, 5, 6, 7]$$$. When $$$i = 3$$$ is chosen, $$$x = |3 + 4 + 5 - 6 - 7| = 1$$$. It can be shown this is the minimum possible value of $$$x$$$.

Example input:
4
2 2
7 2
5 3
1000000000 1000000000

Example output:
1
5
1
347369930

Editorial:
Firefly's Queries
Contest: Codeforces Round 971 (Div. 4)
Difficulty rating: 1700
Tags: bitmasks, data structures, flows, math

Firefly is given an array $$$a$$$ of length $$$n$$$. Let $$$c_i$$$ denote the $$$i$$$'th cyclic shift$$$^{\text{∗}}$$$ of $$$a$$$. She creates a new array $$$b$$$ such that $$$b = c_1 + c_2 + \dots + c_n$$$ where $$$+$$$ represents concatenation$$$^{\text{†}}$$$.

Then, she asks you $$$q$$$ queries. For each query, output the sum of all elements in the subarray of $$$b$$$ that starts from the $$$l$$$-th element and ends at the $$$r$$$-th element, inclusive of both ends.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) — the length of the array and the number of queries.

The following line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq 10^6$$$).

The following $$$q$$$ lines contain two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n^2$$$) — the left and right bounds of the query.

Note that the large inputs may require the use of 64-bit integers.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ and the sum of $$$q$$$ does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each query, output the answer on a new line.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case, $$$b = [1, 2, 3, 2, 3, 1, 3, 1, 2]$$$.

Example input:
5
3 3
1 2 3
1 9
3 5
8 8
5 5
4 8 3 2 4
1 14
3 7
7 10
2 11
1 25
1 1
6
1 1
5 7
3 1 6 10 4
3 21
6 17
2 2
1 5
1 14
9 15
12 13
5 3
4 9 10 10 1
20 25
3 11
20 22

Example output:
18
8
1
55
20
13
41
105
6
96
62
1
24
71
31
14
44
65
15

Editorial:
Yunli's Subarray Queries (easy version)
Contest: Codeforces Round 971 (Div. 4)
Difficulty rating: 1900
Tags: binary search, data structures, two pointers

This is the easy version of the problem. In this version, it is guaranteed that $$$r=l+k-1$$$ for all queries.

For an arbitrary array $$$b$$$, Yunli can perform the following operation any number of times:

- Select an index $$$i$$$. Set $$$b_i = x$$$ where $$$x$$$ is any integer she desires ($$$x$$$ is not limited to the interval $$$[1,n]$$$).

Denote $$$f(b)$$$ as the minimum number of operations she needs to perform until there exists a consecutive subarray$$$^{\text{∗}}$$$ of length at least $$$k$$$ in $$$b$$$.

Yunli is given an array $$$a$$$ of size $$$n$$$ and asks you $$$q$$$ queries. In each query, you must output $$$\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$$$. Note that in this version, you are only required to output $$$f([a_l, a_{l+1}, \ldots, a_{l+k-1}])$$$.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$k$$$, and $$$q$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) — the length of the array, the length of the consecutive subarray, and the number of queries.

The following line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

The following $$$q$$$ lines contain two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$, $$$r=l+k-1$$$) — the bounds of the query.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
Output $$$\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$$$ for each query on a new line.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first query of the first testcase, $$$b=[1,2,3,2,1]$$$. Yunli can make a consecutive subarray of length $$$5$$$ in $$$2$$$ moves:

- Set $$$b_4=4$$$
- Set $$$b_5=5$$$

In the second query of the first testcase, $$$b=[2,3,2,1,2]$$$. Yunli can make a consecutive subarray of length $$$5$$$ in $$$3$$$ moves:

- Set $$$b_3=0$$$
- Set $$$b_2=-1$$$
- Set $$$b_1=-2$$$

Example input:
3
7 5 3
1 2 3 2 1 2 3
1 5
2 6
3 7
8 4 2
4 3 1 1 2 4 3 2
3 6
2 5
5 4 2
4 5 1 2 3
1 4
2 5

Example output:
2
3
2
2
2
2
1

Editorial:
Yunli's Subarray Queries (hard version)
Contest: Codeforces Round 971 (Div. 4)
Difficulty rating: 2200
Tags: binary search, data structures, dp

This is the hard version of the problem. In this version, it is guaranteed that $$$r \geq l+k-1$$$ for all queries.

For an arbitrary array $$$b$$$, Yunli can perform the following operation any number of times:

- Select an index $$$i$$$. Set $$$b_i = x$$$ where $$$x$$$ is any integer she desires ($$$x$$$ is not limited to the interval $$$[1,n]$$$).

Denote $$$f(b)$$$ as the minimum number of operations she needs to perform until there exists a consecutive subarray$$$^{\text{∗}}$$$ of length at least $$$k$$$ in $$$b$$$.

Yunli is given an array $$$a$$$ of size $$$n$$$ and asks you $$$q$$$ queries. In each query, you must output $$$\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$$$.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$k$$$, and $$$q$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) — the length of the array, the length of the consecutive subarray, and the number of queries.

The following line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq n$$$).

The following $$$q$$$ lines contain two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$, $$$r \geq l+k-1$$$) — the bounds of the query.

It is guaranteed the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
Output $$$\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])$$$ for each query on a new line.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the second query of the first testcase, we calculate the following function values:

- $$$f([2,3,2,1,2])=3$$$ because Yunli can set $$$b_3=4$$$, $$$b_4=5$$$, and $$$b_5=6$$$, making a consecutive subarray of size $$$5$$$ in $$$3$$$ moves.
- $$$f([2,3,2,1,2,3])=2$$$ because we can set $$$b_3=0$$$ and $$$b_2=-1$$$, making a consecutive subarray of size $$$5$$$ in $$$2$$$ moves (starting at position $$$2$$$)

The answer to this query is $$$3+2=5$$$.

Example input:
3
7 5 3
1 2 3 2 1 2 3
1 7
2 7
3 7
8 4 2
4 3 1 1 2 4 3 2
3 6
1 5
5 4 2
4 5 1 2 3
1 4
1 5

Example output:
6
5
2
2
5
2
3

Editorial:
Yunli's Subarray Queries (extreme version)
Contest: Codeforces Round 971 (Div. 4)
Difficulty rating: 2700
Tags: data structures, dp, implementation

This is the extreme version of the problem. In this version, the output of each query is different from the easy and hard versions. It is also guaranteed that $$$r \geq l+k-1$$$ for all queries.

For an arbitrary array $$$b$$$, Yunli can perform the following operation any number of times:

- Select an index $$$i$$$. Set $$$b_i = x$$$ where $$$x$$$ is any integer she desires ($$$x$$$ is not limited to the interval $$$[1,n]$$$).

Denote $$$f(b)$$$ as the minimum number of operations she needs to perform until there exists a consecutive subarray$$$^{\text{∗}}$$$ of length at least $$$k$$$ in $$$b$$$.

Yunli is given an array $$$a$$$ of size $$$n$$$ and asks you $$$q$$$ queries. In each query, you must output $$$\sum_{i=l}^{r-k+1} \sum_{j=i+k-1}^{r} f([a_i, a_{i+1}, \ldots, a_j])$$$.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$k$$$, and $$$q$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) — the length of the array, the length of the consecutive subarray, and the number of queries.

The following line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq n$$$).

The following $$$q$$$ lines contain two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$, $$$r \geq l+k-1$$$) — the bounds of the query.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
Output $$$\sum_{i=l}^{r-k+1} \sum_{j=i+k-1}^{r} f([a_i, a_{i+1}, \ldots, a_j])$$$ for each query on a new line.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first query of the first testcase, we can calculate the answer for the query through the following:

- $$$i = 4$$$ and $$$j = 5$$$: $$$f([2, 1])=1$$$ because Yunli can set $$$b_2=3$$$, making a consecutive subarray of size $$$2$$$ in $$$1$$$ move.
- $$$i = 4$$$ and $$$j = 6$$$: $$$f([2, 1, 2])=0$$$ because there is already a consecutive array of size $$$2$$$.
- $$$i = 5$$$ and $$$j = 6$$$: $$$f([1, 2])=0$$$ because there is already a consecutive array of size $$$2$$$.

The answer to this query is $$$1+0+0=1$$$.

Example input:
5
7 2 4
1 2 3 2 1 2 3
4 6
1 7
2 7
3 7
8 4 2
4 3 1 1 2 4 3 2
3 6
1 5
5 4 2
4 5 1 2 3
1 4
1 5
10 4 8
2 3 6 5 8 9 8 10 10 1
2 7
6 10
1 9
1 6
3 9
4 10
2 10
1 8
10 7 4
3 4 5 3 4 5 9 10 8 9
1 9
2 10
1 10
2 9

Example output:
1
3
3
3
2
7
2
4
8
6
28
7
16
20
32
19
18
15
26
9

Editorial:
Find Minimum Operations
Contest: Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
Difficulty rating: 800
Tags: bitmasks, brute force, greedy, math, number theory

You are given two integers $$$n$$$ and $$$k$$$.

In one operation, you can subtract any power of $$$k$$$ from $$$n$$$. Formally, in one operation, you can replace $$$n$$$ by $$$(n-k^x)$$$ for any non-negative integer $$$x$$$.

Find the minimum number of operations required to make $$$n$$$ equal to $$$0$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^9$$$).

Output format:
For each test case, output the minimum number of operations on a new line.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$n = 5$$$ and $$$k = 2$$$. We can perform the following sequence of operations:

1. Subtract $$$2^0 = 1$$$ from $$$5$$$. The current value of $$$n$$$ becomes $$$5 - 1 = 4$$$.
2. Subtract $$$2^2 = 4$$$ from $$$4$$$. The current value of $$$n$$$ becomes $$$4 - 4 = 0$$$.

It can be shown that there is no way to make $$$n$$$ equal to $$$0$$$ in less than $$$2$$$ operations. Thus, $$$2$$$ is the answer.

In the second test case, $$$n = 3$$$ and $$$k = 5$$$. We can perform the following sequence of operations:

1. Subtract $$$5^0 = 1$$$ from $$$3$$$. The current value of $$$n$$$ becomes $$$3 - 1 = 2$$$.
2. Subtract $$$5^0 = 1$$$ from $$$2$$$. The current value of $$$n$$$ becomes $$$2 - 1 = 1$$$.
3. Subtract $$$5^0 = 1$$$ from $$$1$$$. The current value of $$$n$$$ becomes $$$1 - 1 = 0$$$.

It can be shown that there is no way to make $$$n$$$ equal to $$$0$$$ in less than $$$3$$$ operations. Thus, $$$3$$$ is the answer.

Example input:
6
5 2
3 5
16 4
100 3
6492 10
10 1

Example output:
2
3
1
4
21
10

Editorial:
If $$$k$$$ is 1, we can only subtract 1 in each operation, and our answer will be $$$n$$$.
Now, first, it can be seen that we have to apply at least $$$n$$$ mod $$$k$$$ operations of subtracting $$$k^0$$$ (as all the other operations will not change the value of $$$n$$$ mod $$$k$$$). Now, once $$$n$$$ is divisible by $$$k$$$, solving the problem for $$$n$$$ is equivalent to solving the problem for $$$\frac{n}{k}$$$ as subtracting $$$k^0$$$ will be useless because if we apply the $$$k^0$$$ subtraction operation, then $$$n$$$ mod $$$k$$$ becomes $$$k-1$$$, and we have to apply $$$k-1$$$ more operations to make $$$n$$$ divisible by $$$k$$$ (as the final result, i.e., 0 is divisible by $$$k$$$). Instead of doing these $$$k$$$ operations of subtracting $$$k^0$$$, a single operation subtracting $$$k^1$$$ will do the job.
So, our final answer becomes the sum of the digits of $$$n$$$ in base $$$k$$$.
Bitwise Balancing
Contest: Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
Difficulty rating: 1400
Tags: bitmasks, hashing, implementation, math, schedules, ternary search

You are given three non-negative integers $$$b$$$, $$$c$$$, and $$$d$$$.

Please find a non-negative integer $$$a \in [0, 2^{61}]$$$ such that $$$(a\, |\, b)-(a\, \&\, c)=d$$$, where $$$|$$$ and $$$\&$$$ denote the bitwise OR operation and the bitwise AND operation, respectively.

If such an $$$a$$$ exists, print its value. If there is no solution, print a single integer $$$-1$$$. If there are multiple solutions, print any of them.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The only line of each test case contains three positive integers $$$b$$$, $$$c$$$, and $$$d$$$ ($$$0 \le b, c, d \le 10^{18}$$$).

Output format:
For each test case, output the value of $$$a$$$, or $$$-1$$$ if there is no solution. Please note that $$$a$$$ must be non-negative and cannot exceed $$$2^{61}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$(0\,|\,2)-(0\,\&\,2)=2-0=2$$$. So, $$$a = 0$$$ is a correct answer.

In the second test case, no value of $$$a$$$ satisfies the equation.

In the third test case, $$$(12\,|\,10)-(12\,\&\,2)=14-0=14$$$. So, $$$a = 12$$$ is a correct answer.

Example input:
3
2 2 2
4 2 6
10 2 14

Example output:
0
-1
12

Editorial:
The first observation is that the expression $$$a|b - a\&c = d$$$ is bitwise independent. That is, the combination of a tuple of bits of $$$a, b, and\ c$$$ corresponding to the same power of 2 will only affect the bit value of $$$d$$$ at that power of 2 only.
This is because:
1. We are performing subtraction, so extra carry won't be generated to the next power of 2.
2. Any tuple of bits of $$$a, b, and\ c$$$ corresponding to the same power of 2 won't result in -1 for that power of 2. As that would require $$$a|b$$$ to be zero and $$$a\&c$$$ to be one. The former condition requires the bit of $$$a$$$ to be zero, while the latter requires it to be one, which is contradicting.
Now, let us consider all 8 cases of bits of a, b, c and the corresponding bit value of d in the following table:
So, clearly, for different bits of $$$b, c,$$$ and $$$d$$$, we can find the value of the corresponding bit in $$$a$$$, provided it is not the case when bit values of $$$b, c,$$$ and $$$d$$$ are 1,0,0 or 0,1,1, which are not possible; so, in that case, the answer is -1.
Problem Solving
Contest: Kotlin Heroes: Episode 11
Tags: *special

Jane has decided to solve a list of $$$n$$$ problems on Codeforces. The $$$i$$$-th problem in her list has difficulty $$$d_i$$$, and the last problem in the list is the hardest one (for every problem $$$j < n$$$, $$$d_j < d_n$$$).

Jane's problem-solving skill is some integer $$$x$$$ (unknown to you). If a problem's difficulty is greater than $$$x$$$, then Jane cannot solve it, otherwise she can solve it.

Jane has solved all problems form the list, except for the last one — she found out that it was too difficult for her. Can you uniquely determine the value of $$$x$$$ — Jane's problem solving skill?

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case consists of two lines:

- the first line contains one integer $$$n$$$ ($$$2 \le n \le 50$$$) — the number of problems;
- the second line contains $$$n$$$ integers $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_i \le 50$$$).

Additional constraint on the input: in every test case, the last problem is more difficult than every other problem (i. e. $$$d_n > d_j$$$ for every $$$j < n$$$). This means that at least one possible value of $$$x$$$ exists.

Output format:
For each test case, print one line:

- if you can determine the value of $$$x$$$ uniquely, print $$$x$$$;
- otherwise, print Ambiguous. The checking program is case-sensitive, so if you print ambiguous or AMBIGUOUS, your answer will be considered wrong.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the second test case of the example, the value of $$$x$$$ could be $$$11$$$, but it also could be $$$10$$$ (other possible values for $$$x$$$ also exist).

Example input:
3
5
1 2 3 4 5
8
8 8 5 3 4 6 8 12
4
3 3 3 4

Example output:
4
Ambiguous
3

Editorial:
If we want to determine that Jane's skill is $$$x$$$, then there should be a problem of difficulty $$$x$$$ which she solved, and a problem of difficulty $$$x+1$$$ which she didn't. Since the only problem she didn't solve has difficulty $$$d_n$$$, then if $$$x$$$ is unique, it should be equal to $$$d_n-1$$$.
So, let's check if there exists a problem of difficulty $$$d_n - 1$$$ which Jane solved. This can be done in a multitude of ways; the model solution uses the functions dropLast to form a version of the given array without the last element, and contains to check if the resulting array contains the value we need.