2026-2027 Saint-Petersburg Open High School Programming Contest (SpbKOSHP 26)
A. Legs for the Olympiad
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Kostya is preparing a venue for a team olympiad. Each team needs one table and three stools.

Fortunately, the school warehouse has an unlimited number of tabletops and stool seats, but the legs of school furniture often break, so Kostya ordered $$$n$$$ identical legs for tables and stools from a furniture workshop. Each table must have four legs, and each stool must have three legs.

Three school students participate in the team olympiad, so each team needs one table and three stools. Kostya assembles the furniture as follows:

  1. He assembles three stools, if there are enough legs for them.
  2. If he managed to assemble three stools, he assembles one table, if there are enough legs for it.
  3. He repeats steps 1 and 2 while there are enough legs.
  4. If there are not enough legs for step 1 or 2, he assembles the maximum possible number of stools from all remaining legs and stops. These stools will be kept as spares in case something breaks during the olympiad.

Kostya is very busy assembling the furniture, so help him answer the question of how many tables and stools he will be able to assemble.

Input

The first line of input contains the integer $$$n$$$ $$$(1 \le n \le 10^{18})$$$.

Output

Print two integers separated by a space — the number of tables and stools, respectively, that Kostya will be able to assemble.

Examples
Input
3
Output
0 1
Input
18
Output
1 4
B. Safe Key
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

At the Central Bank of Berland, clients store their money and valuables in safe deposit boxes inside a large vault. To enter the vault, a client enters a personal secret code, which consists of $$$n$$$ consecutive non-negative integers.

The bank takes the security of money and valuables very seriously, so it wants clients to change their codes regularly. Some clients do not like changing their codes very much because they keep forgetting them. Forgetful clients make minimal changes to the old code to obtain a new one. To combat this behavior, the bank has made it a paid service to leave a code position unchanged.

Rodion, a regular client of the bank, has his secret code $$$A=[a_1, a_2, \ldots, a_n]$$$ expiring. He has придумал a new secret code $$$B=[b_1, b_2, \ldots, b_n]$$$. The bank's secret code change service works as follows: to transform the old code $$$A$$$ into the new code $$$B$$$, Rodion may perform the following operation any number of times.

Choose an integer $$$k$$$ ($$$0 \le k \lt 40$$$). For each element of the current code $$$A$$$, one of two actions is chosen:

  • replace $$$a_i$$$ with $$$a_i \bmod 2^k$$$ for free;
  • leave $$$a_i$$$ unchanged and pay $$$2^k$$$ coins.

The cost of the operation is the sum of the coins paid for all elements left unchanged in this operation.

Of course, Rodion wants to pay as little as possible for changing the code. Help him find the minimum total cost of operations after which the old code $$$A$$$ becomes equal to the new code $$$B$$$.

If it is impossible to transform code $$$A$$$ into code $$$B$$$, output $$$-1$$$.

Input

The test contains one or more datasets. The first line contains an integer $$$t$$$ — the number of datasets ($$$1 \le t \le 1000$$$). The descriptions of the datasets follow.

The first line of each datasets contains an integer $$$n$$$ — the length of the code ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, and the third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le a_i, b_i \lt 2^{40}$$$).

The sum of $$$n$$$ over all datasets in one test does not exceed $$$2 \cdot 10^5$$$.

Output

For each dataset, output one integer — the minimum total cost of transforming code $$$A$$$ into code $$$B$$$. If the transformation is impossible, output $$$-1$$$.

Example
Input
4
2
1 7
0 1
3
3 1 4
1 5 9
4
13 10 4 4
1 2 4 4
2
1099511627775 549755813888
7 549755813888
Output
1
-1
6
8
Note

In the first example, the following operations can be performed:

  1. Choose $$$k = 2$$$: replace $$$a_1 = 1$$$ with $$$a_1 \bmod 2^2 = 1$$$ and $$$a_2 = 7$$$ with $$$a_2 \bmod 2^2 = 1$$$, after which the code becomes $$$A = [1, 1]$$$. This operation is free.
  2. Choose $$$k = 0$$$: replace $$$a_1 = 1$$$ with $$$a_1 \bmod 2^0 = 0$$$, and leave $$$a_2 = 1$$$ unchanged and pay $$$2^0 = 1$$$ coin. The cost of this operation is $$$1$$$. After this operation, the code becomes $$$A = [0, 1]$$$.

The total cost is $$$1$$$. There is no sequence of operations with smaller cost after which code $$$A$$$ becomes equal to code $$$B$$$.

In the second example, the required transformation is impossible.

C. Pool
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alexander decided to build a swimming pool near his house and asked a team of designers to prepare a design.

The designers proposed a pool in the shape of a convex polygon with vertices at points $$$P_1, P_2, \ldots, P_n$$$. Vertex $$$P_i$$$ has coordinates $$$(x_i, y_i)$$$. The vertices are listed in counterclockwise order; no three vertices lie on the same line. It is known that $$$x_1 \lt x_2 \lt \ldots \lt x_n$$$, all $$$y_i \le 0$$$, and $$$y_1 = y_n = 0$$$.

After estimating the cost of the work, Alexander decided to simplify the project: the new pool must have the shape of a convex polygon with exactly $$$k$$$ vertices. However, the workers have already marked out the site and even started digging, so the location of the pool cannot be chosen arbitrarily. The pool must have the shape of a convex polygon and completely contain the polygon in which the pool was originally planned to be placed. Each side of the pool must lie on one of the lines containing sides of the original polygon. Different sides of the new pool must use different lines. In addition, construction of the wall along side $$$P_1P_2$$$ has already begun, so one side of the new pool must lie on the line passing through vertices $$$P_1$$$ and $$$P_2$$$.

At the same time, Alexander's plot is not very large, so he wants to build a pool of minimum area satisfying these conditions.

The figures below show optimal designs for the new pool for the two examples from the statement. The shaded region denotes the new pool, and the dashed lines — extensions of the sides of the original polygon.

Help him find the minimum possible area of the new pool satisfying all the requirements.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ — the number of vertices of the original polygon and the required number of vertices of the new pool ($$$3 \le k \le n \le 10^5$$$).

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ — the coordinates of vertex $$$P_i$$$ ($$$-10^9 \le x_i \le 10^9$$$, $$$-10^9 \le y_i \le 0$$$).

It is guaranteed that the points are vertices of a convex polygon and are listed in counterclockwise order. No three vertices of the polygon lie on the same line. It is also guaranteed that $$$x_1 \lt x_2 \lt \ldots \lt x_n$$$ and $$$y_1 = y_n = 0$$$.

Output

Print one number — the minimum possible area of the new pool satisfying all the requirements.

The answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Examples
Input
4 3
0 0
1 -1
2 -1
3 0
Output
2.25
Input
4 4
0 0
1 -1
2 -1
3 0
Output
2
Note

In the first example, the new pool must have exactly three sides. The optimal solution is triangle $$$AED$$$. Its sides lie on the lines containing sides $$$AB$$$, $$$CD$$$, and $$$AD$$$ of the original polygon. The area of this triangle is $$$2.25$$$. The resulting pool is shown in the left figure.

In the second example, the new pool must have exactly four sides, so the original polygon can be left unchanged. Its area is $$$2$$$. The resulting pool is shown in the right figure.

D. A+B
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Xeni found three numbers $$$A$$$, $$$B$$$, $$$C$$$ and the equality $$$A + B = C$$$ in her old notebook, which seemed rather suspicious to her.

Xeni realized that the numbers were probably written in some alternative numeral system and decided to find all possible integer bases of numeral systems $$$b \ge 2$$$ for which all three representations are valid and the equality holds. Since there may be many such numeral systems, she decided to compute the sum of their bases.

Help Xeni compute the required sum. If there are infinitely many such bases, report it.

Recall that a representation of a number in a numeral system with base $$$b$$$ is given by an array of digits $$$d_1, d_2, \ldots, d_n$$$, from the most significant digit to the least significant one. It is valid if $$$0 \le d_i \lt b$$$ for all $$$1 \le i \le n$$$. The value of the number specified by digits $$$d_1, d_2, \ldots, d_n$$$ in base $$$b$$$ is equal to $$$$$$\sum_{i=1}^{n} d_i b^{n-i}.$$$$$$ Traditionally, for numeral systems with base greater than $$$10$$$, letters and other symbols are used to write digits, but in this problem we will simply specify the values of each digit in the number representations, without introducing special notation.

Input

The first line contains an integer $$$n_A$$$ — the length of the representation of number $$$A$$$ ($$$1 \le n_A \le 10^5$$$). The second line contains $$$n_A$$$ integers $$$a_1, a_2, \ldots, a_{n_A}$$$ — the values of its digits ($$$0 \le a_i \le 10^9$$$).

The third line contains an integer $$$n_B$$$ — the length of the representation of number $$$B$$$ ($$$1 \le n_B \le 10^5$$$). The fourth line contains $$$n_B$$$ integers $$$b_1, b_2, \ldots, b_{n_B}$$$ — the values of its digits ($$$0 \le b_i \le 10^9$$$).

The fifth line contains an integer $$$n_C$$$ — the length of the representation of number $$$C$$$ ($$$1 \le n_C \le 10^5$$$). The sixth line contains $$$n_C$$$ integers $$$c_1, c_2, \ldots, c_{n_C}$$$ — the values of its digits ($$$0 \le c_i \le 10^9$$$).

The digits of each representation are listed from the most significant digit to the least significant one.

It is guaranteed that the number representations do not contain leading zeros.

Output

In a single line, output the sum of all integer bases $$$b \ge 2$$$ for which the representations of numbers $$$A$$$, $$$B$$$, and $$$C$$$ are valid and the equality $$$A + B = C$$$ holds.

If there are no such bases, output $$$0$$$. If there are infinitely many such bases, output the string "inf".

Examples
Input
2
1 2
1
3
2
2 0
Output
5
Input
2
1 2
2
3 4
2
4 6
Output
inf
Input
2
1 2
1
0
2
2 0
Output
0
E. Future Typewriter
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Danya was appointed the chief editor of the school wall newspaper in a retro style. For authenticity, Danya decided to type it on a typewriter. He could not find an old typewriter, so he ordered a modern programmable typewriter from an online store.

The keyboard of the typewriter consists of $$$m$$$ keys arranged in a row and numbered from $$$1$$$ to $$$m$$$. For the next issue of the wall newspaper, Danya needs to type a text $$$s = s_1 s_2 \ldots s_n$$$, consisting of the first $$$m$$$ lowercase English letters. The typewriter can be programmed for his text. To do this, each of the $$$m$$$ letters must be assigned to exactly one key, and different letters must be placed on different keys. If two consecutive letters of the text are located on keys with numbers $$$x$$$ and $$$y$$$, then the transition time between them is $$$|x - y|$$$. The time to type the first letter is not counted. Thus, if the character $$$c$$$ is located at position $$$p_c$$$, then the total time to type the text is $$$$$$ \sum_{i=1}^{n-1} \left|p_{s_i} - p_{s_{i+1}}\right|. $$$$$$

Danya noticed that the typing time depends on how he assigned the letters on the typewriter. He would like to compute the minimum and maximum possible typing time among all possible keyboard layouts. Danya got too carried away with journalism, so he does not have time to solve this problem himself; help him do it.

Input

The first line of the input contains integers $$$n$$$ and $$$m$$$ — the length of the text and the number of letters in the alphabet ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 20$$$).

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of the first $$$m$$$ lowercase English letters.

Output

Print two integers — the minimum and maximum possible typing time.

Examples
Input
7 3
abacaba
Output
6 10
Input
5 1
aaaaa
Output
0 0
Note

In the first example, there are exactly $$$6$$$ possible assignments of positions for the letters «a», «b», and «c»:

  • If $$$p_{\text{a}} = 1$$$, $$$p_{\text{b}} = 2$$$, $$$p_{\text{c}} = 3$$$: $$$|1 - 2| + |2 - 1| + |1 - 3| + |3 - 1| + |1 - 2| + |2 - 1| = 1 + 1 + 2 + 2 + 1 + 1 = 8$$$.
  • If $$$p_{\text{a}} = 1$$$, $$$p_{\text{b}} = 3$$$, $$$p_{\text{c}} = 2$$$: $$$|1 - 3| + |3 - 1| + |1 - 2| + |2 - 1| + |1 - 3| + |3 - 1| = 2 + 2 + 1 + 1 + 2 + 2 = 10$$$.
  • If $$$p_{\text{a}} = 2$$$, $$$p_{\text{b}} = 1$$$, $$$p_{\text{c}} = 3$$$: $$$|2 - 1| + |1 - 2| + |2 - 3| + |3 - 2| + |2 - 1| + |1 - 2| = 1 + 1 + 1 + 1 + 1 + 1 = 6$$$.
  • If $$$p_{\text{a}} = 2$$$, $$$p_{\text{b}} = 3$$$, $$$p_{\text{c}} = 1$$$: $$$|2 - 3| + |3 - 2| + |2 - 1| + |1 - 2| + |2 - 3| + |3 - 2| = 1 + 1 + 1 + 1 + 1 + 1 = 6$$$.
  • If $$$p_{\text{a}} = 3$$$, $$$p_{\text{b}} = 1$$$, $$$p_{\text{c}} = 2$$$: $$$|3 - 1| + |1 - 3| + |3 - 2| + |2 - 3| + |3 - 1| + |1 - 3| = 2 + 2 + 1 + 1 + 2 + 2 = 10$$$.
  • If $$$p_{\text{a}} = 3$$$, $$$p_{\text{b}} = 2$$$, $$$p_{\text{c}} = 1$$$: $$$|3 - 2| + |2 - 3| + |3 - 1| + |1 - 3| + |3 - 2| + |2 - 3| = 1 + 1 + 2 + 2 + 1 + 1 = 8$$$.

The minimum typing time among all layouts is $$$6$$$, and the maximum is $$$10$$$.

In the second example, there is only one layout, $$$p_{\text{a}} = 1$$$, with typing time $$$0$$$.

F. Stylish Combos
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Sasha wants to join an esports team in his favorite computer game. To do this, he sent a recording of his playthrough of a level in this game, consisting of $$$n$$$ consecutive actions. Each action is uniquely determined by its integer identifier, so the recording is a sequence of integers $$$a_1, a_2, \ldots, a_n$$$.

A contiguous subarray of the recording $$$a_l, a_{l+1}, \ldots, a_r$$$ ($$$1 \le l \le r \le n$$$) is called a stylish combo if the player never repeated the same action inside it — in other words, all numbers $$$a_l, a_{l+1}, \ldots, a_r$$$ are pairwise distinct.

The team recruiters are interested only in unique stylish combos. Two stylish combos $$$a_{l_1}, a_{l_1+1}, \ldots, a_{r_1}$$$ and $$$a_{l_2}, a_{l_2+1}, \ldots, a_{r_2}$$$ are considered the same if they have the same length $$$k = r_1 - l_1 + 1 = r_2 - l_2 + 1$$$ and for every integer $$$j$$$ from $$$0$$$ to $$$k - 1$$$ the equality $$$a_{l_1 + j} = a_{l_2 + j}$$$ holds.

Given the playthrough recording, find the number of different stylish combos Sasha performed.

Input

The first line of the input contains one integer $$$n$$$ — the number of actions in the recording ($$$1 \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the identifiers of the performed actions ($$$1 \le a_i \le 10^{18}$$$).

Output

Print one integer — the number of different stylish combos in the given recording.

Examples
Input
5
2 1 2 1 3
Output
7
Input
4
7 7 7 7
Output
1
Note

In the first example, there are seven different stylish combos in the recording:

  • three combos of one action: $$$[1]$$$, $$$[2]$$$, and $$$[3]$$$;
  • three combos of two actions: $$$[2, 1]$$$, $$$[1, 2]$$$, and $$$[1, 3]$$$;
  • one combo of three actions: $$$[2, 1, 3]$$$.
The subarrays $$$[2, 1, 2]$$$ and $$$[1, 2, 1]$$$ are not stylish combos, because each of them contains repeated actions.

In the second example, all actions are the same, so the only stylish combo is $$$[7]$$$.

G. Another Shuffle
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Alexander bought himself a new deck of cards at a kiosk. The deck he bought contains $$$n$$$ cards, each of which has an integer from $$$0$$$ to $$$10^9$$$ written on it.

Alexander decided to shuffle the deck. Let $$$a_i$$$ be the value of the $$$i$$$-th card from the top of the deck. In one shuffle, Alexander performs the following actions:

  1. Splits the deck into one or more non-empty piles by cutting it between every pair of adjacent cards with equal values, that is, such that $$$a_i = a_{i+1}$$$;
  2. Stacks the piles in reverse order, preserving the order of cards inside each pile.

If there are no two adjacent cards with equal values in the deck, then when Alexander tries to shuffle it using his method, the order of cards in the deck does not change.

Alexander repeats shuffling until he encounters a card order that has already appeared before. He wonders how many shuffles he will perform before this happens. Help him answer this question.

Input

You need to solve the problem for one or more decks. The first line contains one integer $$$t$$$ — the number of decks Alexander has ($$$1 \le t \le 10^5$$$).

The descriptions of the $$$t$$$ decks follow. Each deck description consists of two lines.

The first line contains one integer $$$n$$$ — the number of cards ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ — the initial order of the cards from top to bottom ($$$0 \le a_i \le 10^9$$$).

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

Output

For each deck, output one integer — the minimum number of shuffles after which the order of cards in the deck coincides with one of the previously encountered orders.

Example
Input
3
5
0 1 1 2 2
5
0 1 2 1 0
4
1 2 2 1
Output
2
1
2
Note

In the first deck from the sample, the first shuffle will split it into piles $$$[0, 1]$$$, $$$[1, 2]$$$, $$$[2]$$$. After combining the piles in reverse order, the deck will look like $$$[2, 1, 2, 0, 1]$$$. Now it has no two adjacent equal cards, and after the second shuffle it will not change. In total, two shuffles are performed.

In the second deck, there are no adjacent equal cards from the start, so it will not change after the first shuffle.

After the first shuffle, the third deck becomes $$$[2, 1, 1, 2]$$$, and after the second one it becomes $$$[1, 2, 2, 1]$$$ and coincides with the initial deck.

H. Best Permutation
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

This is an interactive problem.

At a math club, the teacher prepared $$$n$$$ cards with integers and laid them out in a row face down. The number written on the $$$i$$$-th card is $$$a_i$$$, but the students do not know these numbers. Then the students play the following game with the teacher.

The students have $$$n$$$ tokens numbered from $$$1$$$ to $$$n$$$, with each number appearing on exactly one token. The students make at most $$$n$$$ moves. In each move, they choose a permutation $$$[p_1, p_2, \ldots, p_n]$$$ of the numbers from $$$1$$$ to $$$n$$$ and place the tokens on the cards, with the token numbered $$$p_i$$$ placed on the $$$i$$$-th card. In response, the teacher tells the students the value $$$$$$ S(p)=a_1p_1+a_2p_2+\ldots+a_np_n. $$$$$$

The goal of the students is to obtain the maximum possible value of $$$S(p)$$$.

Write a program that will play this game for the students: it should make at most $$$n$$$ queries and find a permutation for which the sum $$$S(p)$$$ is maximum. If there are several such permutations, you may find any of them.

Interaction

The first line contains an integer $$$n$$$ — the length of the hidden array ($$$1 \le n \le 500$$$).

To make a query, output a line of the following form:

? $$$p_1\ p_2\ \ldots\ p_n$$$
The numbers $$$p_1, p_2, \ldots, p_n$$$ must form a permutation of the numbers from 1 to $$$n$$$. In response, the judging program will output one integer — the value of $$$S(p)$$$. Read it before making the next query. In total, you are allowed to make at most $$$n$$$ queries. It is guaranteed that the numbers $$$a_i$$$ on the cards lie in the range from $$$-10^9$$$ to $$$10^9$$$.

When you find a permutation with the maximum possible sum, output a line of the following form:

! $$$p_1\ p_2\ \ldots\ p_n$$$
Then terminate your program. The final answer is not counted as a query; you do not need to wait for a response to it.

Be sure to end every line with a newline character.

After outputting each query and the final answer, you must flush the output buffer: for example, use cout « flush or endl in C++, print(..., flush=True) in Python. A newline without flushing may lead to a time limit exceeded error.

Example
Input
4

21

10

20

19
Output

? 3 1 2 4

? 2 4 1 3

? 4 2 3 1

? 1 3 4 2

! 2 1 4 3
Note

In the example, the hidden array is $$$(2, -1, 4, 2)$$$. In the first query, the permutation $$$(3, 1, 2, 4)$$$ is chosen, so the program responds with the number $$$2\cdot 3+(-1)\cdot 1+4\cdot 2+2\cdot 4=21$$$.

After four queries, the answer $$$(2, 1, 4, 3)$$$ is output. For it, the sum is $$$2\cdot 2+(-1)\cdot 1+4\cdot 4+2\cdot 3=25$$$. A larger sum cannot be obtained. The permutation $$$(3, 1, 4, 2)$$$ is also a correct answer.

Empty lines in the table help show the order of messages. Your program outputs the lines from the right column and reads the responses from the left column.

I. SMS Code
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

For a banking application, it was necessary to develop functionality for autofilling SMS codes. When a user receives a message confirming a transaction, the system must automatically recognize a four-digit numeric code that comes after the separate word CODE, separated by a space.

Input

The only line contains the text of an SMS message of length $$$n$$$, consisting of uppercase Latin letters, digits, and spaces; the length of the string is from $$$9$$$ to $$$10^3$$$. It is guaranteed that the message contains exactly one occurrence of the word CODE, and after it, separated by a space, there is a four-digit code.

Output

Print the extracted four-digit confirmation code.

Examples
Input
1208 RUB IN EIRC SPB LK CODE 4886
Output
4886
Input
MYCODE 1234 CODE 0239
Output
0239
J. Taxi Driver Rating
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

After each ride, a passenger gives the taxi driver an integer rating from one to five. The taxi service calculates the driver's rating based on these ratings. To make the rating reflect recent performance, old rides are not taken into account.

The rating at the end of day $$$d$$$ is calculated as follows:

  1. Rides from the last $$$X$$$ days, including day $$$d$$$, are selected.
  2. If there are more than $$$Y$$$ selected rides, only the last $$$Y$$$ of them remain. Otherwise, all selected rides remain.
  3. The sum of the ratings of the remaining rides is divided by their number. If no rides remain, the rating is zero.

The days and ratings of $$$n$$$ rides are known. The rides are listed in the order they were made, including within the same day. There are also $$$q$$$ queries: each query specifies a day for which the rating at the end of that day must be found. The query days are listed in nondecreasing order and may repeat.

For each query, determine the taxi driver's rating after all rides of the specified day.

Input

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

The first line of each test case contains four integers: $$$n$$$ — the number of rides, $$$q$$$ — the number of queries, $$$X$$$ — how many last days are taken into account, and $$$Y$$$ — the maximum number of rides used in the rating calculation ($$$0 \le n \le 2\cdot 10^5$$$; $$$1 \le q, Y \le 2\cdot 10^5$$$; $$$1 \le X \le 10^9$$$).

Each of the next $$$n$$$ lines contains two integers $$$d_i$$$ and $$$a_i$$$ — the day and the rating of the $$$i$$$-th ride ($$$1 \le d_i \le 10^9$$$; $$$1 \le a_i \le 5$$$). The rides are listed in the order they were made: $$$d_1 \le d_2 \le \ldots \le d_n$$$. The order of lines with the same day matches the order of rides on that day.

Each of the next $$$q$$$ lines contains an integer $$$b_j$$$ — the day of the $$$j$$$-th query ($$$1 \le b_j \le 10^9$$$). The queries are listed in nondecreasing order of day number: $$$b_1 \le b_2 \le \ldots \le b_q$$$.

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

Output

For each test case, output the answers to all $$$q$$$ queries in the same order as they are given. Print each answer on a separate line.

The answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, if your answer is $$$v$$$ and the correct answer is $$$u$$$, the inequality $$$|v-u| \le 10^{-6}\cdot\max(1, |u|)$$$ must hold.

Example
Input
2
6 5 2 3
2 5
2 1
3 4
3 2
3 5
6 1
1
2
3
7
8
0 1 2 3
1
Output
0.000000000
3.000000000
3.666666667
1.000000000
0.000000000
0.000000000
Note

In the first test case, $$$X=2$$$ and $$$Y=3$$$: at most the last three rides from the current and previous days are taken into account.

At the end of the first day, there are no rides yet, so the rating is zero. At the end of the second day, both rides of that day are taken into account, and the rating is $$$(5+1)/2=3$$$.

At the end of the third day, five rides have accumulated over the last two days. Among them, the last three are selected, with ratings four, two, and five. The rating is $$$(4+2+5)/3=11/3$$$.

At the end of the seventh day, rides from the sixth and seventh days are taken into account. There is only one such ride, with rating one. At the end of the eighth day, the sixth and seventh days are taken into account, but there were no rides on those days. Therefore, the rating is zero again.

In the second test case, there are no rides.

K. XOR Moves
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Vanya has learned about XOR and now presses this button on his calculator whenever he gets the chance. The screen currently shows $$$a$$$, but Vanya wants it to show $$$b$$$. Unfortunately, his calculator is rather stubborn: it only lets him XOR with integers from zero to $$$k$$$, inclusive.

In one move, Vanya chooses an integer $$$x$$$ ($$$0 \le x \le k$$$) and replaces the number $$$a$$$ on the screen with $$$a \oplus x$$$. Here, $$$\oplus$$$ denotes XOR.

To compute the XOR of two non-negative integers, write them in binary. If their representations have different lengths, add leading zeros to the shorter one. Each bit of the result is one if the corresponding bits of the two integers differ, and zero if they are equal. For example, five and three are written as $$$101$$$ and $$$011$$$ in binary, so their XOR is $$$110$$$, which is six.

Determine the minimum number of moves Vanya needs to obtain $$$b$$$, or report that this is impossible.

Input

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

Each of the following $$$t$$$ lines contains three integers $$$a$$$, $$$b$$$, and $$$k$$$ ($$$0 \le a, b, k \le 10^9$$$).

Output

For each test case, output one integer: the minimum number of moves needed to make $$$a$$$ equal to $$$b$$$, or $$$-1$$$ if this is impossible.

Example
Input
6
5 5 0
5 2 7
0 7 4
0 8 7
3 4 0
8 9 1
Output
0
1
2
-1
-1
1
Note

In the first test case, $$$a$$$ is already equal to $$$b$$$, so no moves are needed.

In the second test case, choose $$$x = 7$$$: $$$5 \oplus 7 = 2$$$.

In the third test case, two moves suffice: $$$0 \oplus 4 = 4$$$, then $$$4 \oplus 3 = 7$$$. One move cannot suffice because $$$7 \gt k$$$.

In the fourth test case, every allowed $$$x$$$ is less than eight, so no move can change the bit corresponding to eight.

In the fifth test case, the only allowed value is $$$x = 0$$$, which leaves $$$a$$$ unchanged.

In the sixth test case, choose $$$x = 1$$$: $$$8 \oplus 1 = 9$$$.

L. Infinite Pyramid
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Vanya decided to build an infinite pyramid of red and blue cubes according to a special rule.

The rows of the pyramid are numbered from bottom to top, starting from one, and the cubes in each row are numbered from left to right, also starting from one. In the first row (the base of the pyramid), the cubes are arranged in groups of alternating colors: first comes one red cube, then two blue cubes, then three red cubes, then four blue cubes, and so on — the $$$i$$$-th group consists of $$$i$$$ cubes of one color.

Each next row is built on top of the previous one: for each $$$k \ge 1$$$, the cube in the $$$n$$$-th row ($$$n \ge 2$$$) at position $$$k$$$ is placed exactly halfway above the cubes at positions $$$k$$$ and $$$k + 1$$$ of the $$$(n - 1)$$$-th row. The color of the new cube is chosen according to the following rule:

  • if the two cubes below it have the same color, then a red cube is placed on them;
  • if the two cubes below it have different colors, then a blue cube is placed on them.

Unfortunately, there were not enough cubes to finish building the infinite pyramid, but Vanya is very interested in which colors the cubes would have in certain positions.

Given the row number $$$n$$$ and the position $$$k$$$, determine the color of the corresponding cube for each query.

Input

The first line contains an integer $$$q$$$ — the number of queries ($$$1 \le q \le 10^5$$$). The next $$$q$$$ lines contain two numbers $$$n$$$ and $$$k$$$ each — the row and the position of the cube in that row whose color needs to be determined ($$$1 \le n \le 10^5$$$; $$$1 \le k \le 10^{18}$$$).

Output

For each query, output "R" on a separate line if the cube at the specified position is red, and "B" otherwise.

Example
Input
10
1 1
1 2
1 3
1 4
2 1
2 2
2 3
3 1
3 2
4 1
Output
R
B
B
R
B
R
B
B
B
R
Note

The figure shows a fragment of the pyramid consisting of ten cubes, with the base on the first four cubes of the first row:

In the first row ($$$n = 1$$$), first comes a group of one red cube at position $$$1$$$, then a group of two blue cubes at positions $$$2$$$ and $$$3$$$, after which a group of three red cubes begins (the figure shows its first cube at position $$$4$$$).

In the second row ($$$n = 2$$$):

  • cube $$$(2, 1)$$$ is above cubes $$$(1, 1)$$$ and $$$(1, 2)$$$ of different colors, so it is blue ("B");
  • cube $$$(2, 2)$$$ is above two blue cubes $$$(1, 2)$$$ and $$$(1, 3)$$$, so it is red ("R");
  • cube $$$(2, 3)$$$ is above cubes $$$(1, 3)$$$ and $$$(1, 4)$$$ of different colors, so it is blue ("B").

The colors of the cubes in rows $$$n = 3$$$ and $$$4$$$ are determined similarly.