vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The story of Harry Potter begins when Lord Voldemort arrives at his house at Privet Drive. Harry's house has N rooms placed in one line. Each room has its own energy level and no two rooms have exactly same energy. Lord Voldemort arrives at the room which has lowest energy while Harry is at the room having highest energy.

Lord Voldemort has to reach Harry's room. Voldemort can travel from a room having energy X to any other room having energy Y such that |X-Y| is minimum and that room hasn't been visited before. The energy required for moving from room having energy X to room having energy Y is X*Y.

Since Lord Voldemort is busy practicing Avada Kedavra to kill Harry, so he asks you to find the energy required to reach Harry's room.

------ Input ------ 

The first line of input contains 1 integer N denoting the number of rooms.
The second line contains N space separated integers denoting energy levels of each room.

------ Output ------ 

Print the required energy.

------ Constraints ------ 

$2 ≤ N ≤ 1000$
$1 ≤ E_{i} ≤ 10000$

----- Sample Input 1 ------ 
3
4 2 1
----- Sample Output 1 ------ 
10
----- explanation 1 ------ 
Lord Voldemort arrives at room 3 and Harry is in room 1.

Total energy consumed = 1*2 + 2*4 = 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has decided to hold fastest-finger-fast quiz games. Kizahashi, who is in charge of making the scoreboard, is struggling to write the program that manages the players' scores in a game, which proceeds as follows.
A game is played by N players, numbered 1 to N. At the beginning of a game, each player has K points.
When a player correctly answers a question, each of the other N-1 players receives minus one (-1) point. There is no other factor that affects the players' scores.
At the end of a game, the players with 0 points or lower are eliminated, and the remaining players survive.
In the last game, the players gave a total of Q correct answers, the i-th of which was given by Player A_i.
For Kizahashi, write a program that determines whether each of the N players survived this game.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 10^5
 - 1 \leq K \leq 10^9
 - 1 \leq Q \leq 10^5
 - 1 \leq A_i \leq N\ (1 \leq i \leq Q)

-----Input-----
Input is given from Standard Input in the following format:
N K Q
A_1
A_2
.
.
.
A_Q

-----Output-----
Print N lines. The i-th line should contain Yes if Player i survived the game, and No otherwise.

-----Sample Input-----
6 3 4
3
1
3
2

-----Sample Output-----
No
No
Yes
No
No
No

In the beginning, the players' scores are (3, 3, 3, 3, 3, 3).
 - Player 3 correctly answers a question. The players' scores are now (2, 2, 3, 2, 2, 2).
 - Player 1 correctly answers a question. The players' scores are now (2, 1, 2, 1, 1, 1).
 - Player 3 correctly answers a question. The players' scores are now (1, 0, 2, 0, 0, 0).
 - Player 2 correctly answers a question. The players' scores are now (0, 0, 1, -1, -1, -1).
Players 1, 2, 4, 5 and 6, who have 0 points or lower, are eliminated, and Player 3 survives this game.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We take a line segment of length $\textbf{C}$ on a one-dimensional plane and bend it to create a circle with circumference $\textbf{C}$ that's indexed from $0$ to $\boldsymbol{c-1}$. For example, if $c=4$:

We denote a pair of points, $a$ and $\boldsymbol{b}$, as $\rho(a,b)$. We then plot $n$ pairs of points (meaning a total of $2\cdot n$ individual points) at various indices along the circle's circumference. We define the distance $d(a,b)$ between points $a$ and $\boldsymbol{b}$ in pair $\rho(a,b)$ as $min(|a-b|,c-|a-b|)$.

Next, let's consider two pairs: $\rho(a_i,b_i)$ and $\rho(a_j,b_j)$. We define distance $d(\rho(a_i,b_i),\rho(a_j,b_j))$ as the minimum of the six distances between any two points among points $a_i$, $b_i$, $a_j$, and $b_j$. In other words: 
$d(\rho_i,\rho_j)=min(d(a_i,a_j),d(a_i,b_i),d(a_i,b_j),d(b_i,b_j),d(a_j,b_i),d(a_j,b_j))$

For example, consider the following diagram in which the relationship between points in pairs at non-overlapping indices is shown by a connecting line:

Given $n$ pairs of points and the value of $\textbf{C}$, find and print the maximum value of $d(\rho_i,\rho_j)$, where $i\neq j$, among all pairs of points.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ (the number of pairs of points) and $\textbf{C}$ (the circumference of the circle). 

Each line $\boldsymbol{i}$ of the $n$ subsequent lines contains two space-separated integers describing the values of $a_i$ and $b_i$ (i.e., the locations of the points in pair $\boldsymbol{i}$).

Constraints

$1\leq c\leq10^6$
$2\leq n\leq10^5$
$0\leq a,b<c$

Output Format

Print a single integer denoting the maximum $d(\rho_i$, $\rho_j)$, where $i\neq j$.

Sample Input 0
5 8
0 4
2 6
1 5
3 7
4 4

Sample Output 0
2

Explanation 0

In the diagram below, the relationship between points in pairs at non-overlapping indices is shown by a connecting line:

As you can see, the maximum distance between any two pairs of points is $2$, so we print $2$ as our answer.

Sample Input 1
2 1000
0 10
10 20

Sample Output 1
0

Explanation 1

In the diagram below, we have four individual points located at three indices:

Because two of the points overlap, the minimum distance between the two pairs of points is $0$. Thus, we print $0$ as our answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On his birthday, John’s parents made him a huge birthday cake! Everyone had a wonderful dinner, and now it’s time to eat the cake. There are $n$ candles on the cake. John wants to divide the cake into $n$ pieces so that each piece has exactly one candle on it, and there are no left-over pieces. For that, he made $m$ cuts across the cake. Could you help check if John’s cuts successfully divide the candles on the cake?

Formally, the cake is a circle of radius $r$ centered at $(0, 0)$. The candles are $n$ distinct points located strictly inside the circle. Each cut is a straight line $ax + by + c = 0$, described by three coefficients $a$, $b$, and $c$.

-----Input-----
Input starts with three integers $n$ ($1 \leq n \leq 50$), $m$ ($1 \leq m \leq 15$), and $r$ ($1 \leq r \leq 100$) on the first line.

The next $n$ lines give the locations of the candles. Each line has two integers $x$ and $y$ giving the coordinates of one candle ($0 \leq \sqrt {x^2 + y^2} < r$).

The next $m$ lines give the coefficients of the cutting lines. Each line has three integers $a$, $b$, and $c$ ($0 \leq |a|, |b| \leq 100, 0 \leq |c| \leq 20000$) describing a line of the form $ax + by + c = 0$. The values $a$ and $b$ are not both zero.

All candles and lines are distinct. No candle is on a cut line. No line is completely outside or tangent to the cake. The input guarantees that the number of cake pieces remains the same if any cut line is shifted by at most $10^{-4}$ in any direction. The input also guarantees that each candle remains in the interior of the same piece of cake if its position is shifted by at most $10^{-4}$ in any direction.

-----Output-----
Output “yes” if John’s cuts successfully divide the cake so that each piece he obtains has exactly one candle on it. Otherwise, output “no”.

-----Examples-----
Sample Input 1:
4 2 3
0 1
1 0
-1 0
0 -1
-1 1 0
2 1 0
Sample Output 1:
yes

Sample Input 2:
4 3 3
0 1
1 2
-1 2
0 -1
-1 1 -2
-1 -1 2
0 -1 0
Sample Output 2:
no

Sample Input 3:
3 2 3
2 1
0 0
-1 -2
1 1 -2
3 6 12
Sample Output 3:
yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Berland National Library has recently been built in the capital of Berland. In addition, in the library you can take any of the collected works of Berland leaders, the library has a reading room.

Today was the pilot launch of an automated reading room visitors' accounting system! The scanner of the system is installed at the entrance to the reading room. It records the events of the form "reader entered room", "reader left room". Every reader is assigned a registration number during the registration procedure at the library — it's a unique integer from 1 to 10^6. Thus, the system logs events of two forms:  "+ r_{i}" — the reader with registration number r_{i} entered the room;  "- r_{i}" — the reader with registration number r_{i} left the room. 

The first launch of the system was a success, it functioned for some period of time, and, at the time of its launch and at the time of its shutdown, the reading room may already have visitors.

Significant funds of the budget of Berland have been spent on the design and installation of the system. Therefore, some of the citizens of the capital now demand to explain the need for this system and the benefits that its implementation will bring. Now, the developers of the system need to urgently come up with reasons for its existence.

Help the system developers to find the minimum possible capacity of the reading room (in visitors) using the log of the system available to you.


-----Input-----

The first line contains a positive integer n (1 ≤ n ≤ 100) — the number of records in the system log. Next follow n events from the system journal in the order in which the were made. Each event was written on a single line and looks as "+ r_{i}" or "- r_{i}", where r_{i} is an integer from 1 to 10^6, the registration number of the visitor (that is, distinct visitors always have distinct registration numbers).

It is guaranteed that the log is not contradictory, that is, for every visitor the types of any of his two consecutive events are distinct. Before starting the system, and after stopping the room may possibly contain visitors.


-----Output-----

Print a single integer — the minimum possible capacity of the reading room.


-----Examples-----
Input
6
+ 12001
- 12001
- 1
- 1200
+ 1
+ 7

Output
3
Input
2
- 1
- 2

Output
2
Input
2
+ 1
- 1

Output
1


-----Note-----

In the first sample test, the system log will ensure that at some point in the reading room were visitors with registration numbers 1, 1200 and 12001. More people were not in the room at the same time based on the log. Therefore, the answer to the test is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Cracking the Code

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The protection of a popular program developed by one of IT City companies is organized the following way. After installation it outputs a random five digit number which should be sent in SMS to a particular phone number. In response an SMS activation code arrives.

A young hacker Vasya disassembled the program and found the algorithm that transforms the shown number into the activation code. Note: it is clear that Vasya is a law-abiding hacker, and made it for a noble purpose — to show the developer the imperfection of their protection.

The found algorithm looks the following way. At first the digits of the number are shuffled in the following order &lt;first digit&gt;&lt;third digit&gt;&lt;fifth digit&gt;&lt;fourth digit&gt;&lt;second digit&gt;. For example the shuffle of 12345 should lead to 13542. On the second stage the number is raised to the fifth power. The result of the shuffle and exponentiation of the number 12345 is 455 422 043 125 550 171 232. The answer is the 5 last digits of this result. For the number 12345 the answer should be 71232.

Vasya is going to write a keygen program implementing this algorithm. Can you do the same?

Input Specification:
The only line of the input contains a positive integer five digit number for which the activation code should be found.

Output Specification:
Output exactly 5 digits without spaces between them — the found activation code of the program.

Demo Input:
['12345\n']

Demo Output:
['71232']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A **Seven Segment Display** is an electronic display device, used to display decimal or hexadecimal numerals. It involves seven led segments that are lit in specific combinations to represent a specific numeral. An example of each combination is shown below:

![seven segment display](https://upload.wikimedia.org/wikipedia/commons/9/97/7-segments_Indicator.gif)

For this Kata, you must accept an integer in the range `0 - 999999` and print it as a string (in decimal format), with each digit being represented as its own seven segment display (6x seven segment displays in total). Each of the individual led segments per display should be represented by three hashes `###`. Vertical bars `|` (ASCII 124) represent the edges of each display, with a single whitespace on either side between the edge and the area of the led segments. An example of the expected output is shown below:
```
segment_display(123456) = 
|       |  ###  |  ###  |       |  ###  |  ###  | 
|     # |     # |     # | #   # | #     | #     |
|     # |     # |     # | #   # | #     | #     |
|     # |     # |     # | #   # | #     | #     |
|       |  ###  |  ###  |  ###  |  ###  |  ###  |
|     # | #     |     # |     # |     # | #   # |
|     # | #     |     # |     # |     # | #   # |
|     # | #     |     # |     # |     # | #   # |
|       |  ###  |  ###  |       |  ###  |  ###  |
```
For clarity, the entire set of required combinations is provided below:

```
|  ###  |       |  ###  |  ###  |       |  ###  |  ###  |  ###  |  ###  |  ###  |
| #   # |     # |     # |     # | #   # | #     | #     |     # | #   # | #   # |
| #   # |     # |     # |     # | #   # | #     | #     |     # | #   # | #   # |
| #   # |     # |     # |     # | #   # | #     | #     |     # | #   # | #   # |
|       |       |  ###  |  ###  |  ###  |  ###  |  ###  |       |  ###  |  ###  |
| #   # |     # | #     |     # |     # |     # | #   # |     # | #   # |     # |
| #   # |     # | #     |     # |     # |     # | #   # |     # | #   # |     # |
| #   # |     # | #     |     # |     # |     # | #   # |     # | #   # |     # |
|  ###  |       |  ###  |  ###  |       |  ###  |  ###  |       |  ###  |  ###  |
```
If the number is smaller than 6 digits, the result should be justified to the right, with the unused segments being blank (as they are not turned on). Refer to the sample test for an example.

**Note:** There should not be any trailing whitespace for any line.

Please rate and enjoy!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has a favorite sequence a[1 ... n] consisting of n integers. He wrote it out on the whiteboard as follows:

  * he wrote the number a_1 to the left side (at the beginning of the whiteboard); 
  * he wrote the number a_2 to the right side (at the end of the whiteboard); 
  * then as far to the left as possible (but to the right from a_1), he wrote the number a_3; 
  * then as far to the right as possible (but to the left from a_2), he wrote the number a_4; 
  * Polycarp continued to act as well, until he wrote out the entire sequence on the whiteboard. 

<image> The beginning of the result looks like this (of course, if n ≥ 4).

For example, if n=7 and a=[3, 1, 4, 1, 5, 9, 2], then Polycarp will write a sequence on the whiteboard [3, 4, 5, 2, 9, 1, 1].

You saw the sequence written on the whiteboard and now you want to restore Polycarp's favorite sequence.

Input

The first line contains a single positive integer t (1 ≤ t ≤ 300) — the number of test cases in the test. Then t test cases follow.

The first line of each test case contains an integer n (1 ≤ n ≤ 300) — the length of the sequence written on the whiteboard.

The next line contains n integers b_1, b_2,…, b_n (1 ≤ b_i ≤ 10^9) — the sequence written on the whiteboard.

Output

Output t answers to the test cases. Each answer — is a sequence a that Polycarp wrote out on the whiteboard.

Example

Input


6
7
3 4 5 2 9 1 1
4
9 2 7 1
11
8 4 3 1 2 7 8 7 9 4 2
1
42
2
11 7
8
1 1 1 1 1 1 1 1


Output


3 1 4 1 5 9 2 
9 1 2 7 
8 2 4 4 3 9 1 7 2 8 7 
42 
11 7 
1 1 1 1 1 1 1 1 

Note

In the first test case, the sequence a matches the sequence from the statement. The whiteboard states after each step look like this:

[3] ⇒ [3, 1] ⇒ [3, 4, 1] ⇒ [3, 4, 1, 1] ⇒ [3, 4, 5, 1, 1] ⇒ [3, 4, 5, 9, 1, 1] ⇒ [3, 4, 5, 2, 9, 1, 1].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Little Elephant loves chess very much. 

One day the Little Elephant and his friend decided to play chess. They've got the chess pieces but the board is a problem. They've got an 8 × 8 checkered board, each square is painted either black or white. The Little Elephant and his friend know that a proper chessboard doesn't have any side-adjacent cells with the same color and the upper left cell is white. To play chess, they want to make the board they have a proper chessboard. For that the friends can choose any row of the board and cyclically shift the cells of the chosen row, that is, put the last (rightmost) square on the first place in the row and shift the others one position to the right. You can run the described operation multiple times (or not run it at all).

For example, if the first line of the board looks like that "BBBBBBWW" (the white cells of the line are marked with character "W", the black cells are marked with character "B"), then after one cyclic shift it will look like that "WBBBBBBW".

Help the Little Elephant and his friend to find out whether they can use any number of the described operations to turn the board they have into a proper chessboard.


-----Input-----

The input consists of exactly eight lines. Each line contains exactly eight characters "W" or "B" without any spaces: the j-th character in the i-th line stands for the color of the j-th cell of the i-th row of the elephants' board. Character "W" stands for the white color, character "B" stands for the black color.

Consider the rows of the board numbered from 1 to 8 from top to bottom, and the columns — from 1 to 8 from left to right. The given board can initially be a proper chessboard.


-----Output-----

In a single line print "YES" (without the quotes), if we can make the board a proper chessboard and "NO" (without the quotes) otherwise.


-----Examples-----
Input
WBWBWBWB
BWBWBWBW
BWBWBWBW
BWBWBWBW
WBWBWBWB
WBWBWBWB
BWBWBWBW
WBWBWBWB

Output
YES

Input
WBWBWBWB
WBWBWBWB
BBWBWWWB
BWBWBWBW
BWBWBWBW
BWBWBWWW
BWBWBWBW
BWBWBWBW

Output
NO



-----Note-----

In the first sample you should shift the following lines one position to the right: the 3-rd, the 6-th, the 7-th and the 8-th.

In the second sample there is no way you can achieve the goal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The European Space Agency has $N$ telescopes observing distant planets. They have classified $M$ different types of events. They noticed that every day on each planet there is exactly one type of event. They measure events in days because they discovered each event lasts at least one day, and at most 365 days. Events last only complete numbers of days, they never last a fractional part of a day. Each event of the same type lasts exactly the same number of days every time it occurs, regardless of the planet it occurs on.

After many years of observation they want to analyze data. The telescopes logged all observations, but unfortunately they forgot to write down the year the observations took place! Each telescope entry consists of start date, end date and the number of events observed of each type. Given all observations on all the planets, calculate the duration of each type of event. Note that the telescopes are super precise and start working exactly when the event starts and end when an event ends, not necessarily the same one.

Note: for this task, each year has exactly 365 days.

-----Input-----
The first line contains $N$ and $M$ ($1 \le N, M \le 200$) - the number of telescopes and the number of event types. The next $N$ lines each contains $M + 4$ numbers each:

$D_1\text { }M_1\text { }D_2\text { }M_2\text { }F_1\text { }F_2\text { }...\text { }F_ M$

where $D_1, M_1$ ($01 \le D \le 31, 01 \le M \le 12$) is the start date, $D_2, M_2$ is the end date and $F_ i$ ($0 \le F_ i \le 200$) is the number of times event $I$ was observed.

Note that the days $D_ i$ and months $M_ i$ will always be zero-padded to exactly 2 characters.

-----Output-----
One line containing $M$ numbers, the durations of the event types. If more than one solution exists, output any one. If no solution exists, output “-1” (without quotes).

-----Examples-----
Sample Input 1:
1 1
26 02 03 03 1
Sample Output 1:
5

Sample Input 2:
1 1
26 02 03 03 2
Sample Output 2:
185

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Hamburgers

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus loves hamburgers very much. He especially adores the hamburgers he makes with his own hands. Polycarpus thinks that there are only three decent ingredients to make hamburgers from: a bread, sausage and cheese. He writes down the recipe of his favorite "Le Hamburger de Polycarpus" as a string of letters 'B' (bread), 'S' (sausage) и 'C' (cheese). The ingredients in the recipe go from bottom to top, for example, recipe "ВSCBS" represents the hamburger where the ingredients go from bottom to top as bread, sausage, cheese, bread and sausage again.

Polycarpus has *n**b* pieces of bread, *n**s* pieces of sausage and *n**c* pieces of cheese in the kitchen. Besides, the shop nearby has all three ingredients, the prices are *p**b* rubles for a piece of bread, *p**s* for a piece of sausage and *p**c* for a piece of cheese.

Polycarpus has *r* rubles and he is ready to shop on them. What maximum number of hamburgers can he cook? You can assume that Polycarpus cannot break or slice any of the pieces of bread, sausage or cheese. Besides, the shop has an unlimited number of pieces of each ingredient.

Input Specification:
The first line of the input contains a non-empty string that describes the recipe of "Le Hamburger de Polycarpus". The length of the string doesn't exceed 100, the string contains only letters 'B' (uppercase English B), 'S' (uppercase English S) and 'C' (uppercase English C).

The second line contains three integers *n**b*, *n**s*, *n**c* (1<=≤<=*n**b*,<=*n**s*,<=*n**c*<=≤<=100) — the number of the pieces of bread, sausage and cheese on Polycarpus' kitchen. The third line contains three integers *p**b*, *p**s*, *p**c* (1<=≤<=*p**b*,<=*p**s*,<=*p**c*<=≤<=100) — the price of one piece of bread, sausage and cheese in the shop. Finally, the fourth line contains integer *r* (1<=≤<=*r*<=≤<=1012) — the number of rubles Polycarpus has.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output Specification:
Print the maximum number of hamburgers Polycarpus can make. If he can't make any hamburger, print 0.

Demo Input:
['BBBSSC\n6 4 1\n1 2 3\n4\n', 'BBC\n1 10 1\n1 10 1\n21\n', 'BSC\n1 1 1\n1 1 3\n1000000000000\n']

Demo Output:
['2\n', '7\n', '200000000001\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.