vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A bitstring is a string that contains only the characters 0 and 1.

Koyomi Kanou is working hard towards her dream of becoming a writer. To practice, she decided to participate in the Binary Novel Writing Contest. The writing prompt for the contest consists of three bitstrings of length 2n. A valid novel for the contest is a bitstring of length at most 3n that contains at least two of the three given strings as subsequences.

Koyomi has just received the three prompt strings from the contest organizers. Help her write a valid novel for the contest.

A string a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly, zero) characters.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10^5).

Each of the following three lines contains a bitstring of length 2n. It is guaranteed that these three strings are pairwise distinct.

It is guaranteed that the sum of n across all test cases does not exceed 10^5.

Output

For each test case, print a single line containing a bitstring of length at most 3n that has at least two of the given bitstrings as subsequences.

It can be proven that under the constraints of the problem, such a bitstring always exists.

If there are multiple possible answers, you may output any of them.

Example

Input


2
1
00
11
01
3
011001
111010
010001


Output


010
011001010

Note

In the first test case, the bitstrings 00 and 01 are subsequences of the output string: 010 and 010. Note that 11 is not a subsequence of the output string, but this is not required.

In the second test case all three input strings are subsequences of the output string: 011001010, 011001010 and 011001010.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The mayor of RMRCity wants to create a secure landline telephone network for emergency use in case of serious disasters when the city is cut off from the outside world. Some pairs of buildings in the city can be directly connected with a wire telephone line and the municipality engineers have prepared an estimate of the cost of connecting any such pair.

The mayor needs your help to find the cheapest network that connects all buildings in the city and satisfies a particular security measure that will be explained shortly. A call from a building $A$ to another building $B$ may be routed through any simple path in the network (i.e., a path that does not have any repeated building). There are also some insecure buildings that one or more persons with serious criminal records live in. The mayor wants only communications intended for these insecure buildings to reach them. In other words, no communication from any building $A$ to any building $B$ should pass through any insecure building $C$ in the network (where $C$ is different from $A$ and $B$).

-----Input-----
The input consists of a single test case. The first line contains three integers $n$, $m$, $p$ where $1 \le n \le 1000$ is the number of buildings, $0 \le m \le 100000$ is the number of possible direct connections between a pair of buildings, and $0 \le p \le n$ is the number of insecure buildings. The buildings are numbered from $1$ to $n$. The second line contains $p$ distinct integers between $1$ and $n$ (inclusive), which are the numbers of insecure buildings. Each of the next $m$ lines contains three integers $x_ i$, $y_ i$, and $\ell _ i$ describing one potential direct line, where $x_ i$ and $y_ i$ $(1 \le x_ i, y_ i \le n)$ are the distinct buildings the line connects, and $\ell _ i$ $(1 \le \ell _ i \le 10000)$ is the estimate of the cost of connecting these buildings. There is at most one direct link between any two buildings in these $m$ lines.

-----Output-----
Display the cost of the cheapest network satisfying the security measure if it is possible. Otherwise, display impossible.

-----Examples-----
Sample Input:
4 6 1
1
1 2 1
1 3 1
1 4 1
2 3 2
2 4 4
3 4 3
Sample Output:
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob needs a fast way to calculate the volume of a cuboid with three values: `length`, `width` and the `height` of the cuboid. Write a function to help Bob with this calculation.

```if:shell
In bash the script is ran with the following 3 arguments:
`length` `width` `height`
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Given a position of a knight on the standard chessboard, find the number of different moves the knight can perform.

 The knight can move to a square that is two squares horizontally and one square vertically, or two squares vertically and one square horizontally away from it. The complete move therefore looks like the letter L. Check out the image below to see all valid moves for a knight piece that is placed on one of the central squares.

 ![](https://codefightsuserpics.s3.amazonaws.com/tasks/chessKnight/img/knight.jpg?_tm=1473533979951)

# Example

 For `cell = "a1"`, the output should be `2`.

 ![](https://codefightsuserpics.s3.amazonaws.com/tasks/chessKnight/img/ex_1.jpg?_tm=1473533980197)

 For `cell = "c2"`, the output should be `6`.

 ![](https://codefightsuserpics.s3.amazonaws.com/tasks/chessKnight/img/ex_2.jpg?_tm=1473533980368)

# Input/Output


 - `[input]` string `cell`

    String consisting of letter+number - coordinates of the knight on an 8 × 8 chessboard in chess notation.


 - `[output]` an integer

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp invited all his friends to the tea party to celebrate the holiday. He has *n* cups, one for each of his *n* friends, with volumes *a*1,<=*a*2,<=...,<=*a**n*. His teapot stores *w* milliliters of tea (*w*<=≤<=*a*1<=+<=*a*2<=+<=...<=+<=*a**n*). Polycarp wants to pour tea in cups in such a way that:
 -  Every cup will contain tea for at least half of its volume -  Every cup will contain integer number of milliliters of tea -  All the tea from the teapot will be poured into cups -  All friends will be satisfied. 
Friend with cup *i* won't be satisfied, if there exists such cup *j* that cup *i* contains less tea than cup *j* but *a**i*<=&gt;<=*a**j*.

For each cup output how many milliliters of tea should be poured in it. If it's impossible to pour all the tea and satisfy all conditions then output -1.

Input Specification:
The first line contains two integer numbers *n* and *w* (1<=≤<=*n*<=≤<=100, ).

The second line contains *n* numbers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=100).

Output Specification:
Output how many milliliters of tea every cup should contain. If there are multiple answers, print any of them.

If it's impossible to pour all the tea and satisfy all conditions then output -1.

Demo Input:
['2 10\n8 7\n', '4 4\n1 1 1 1\n', '3 10\n9 8 10\n']

Demo Output:
['6 4 \n', '1 1 1 1 \n', '-1\n']

Note:
In the third example you should pour to the first cup at least 5 milliliters, to the second one at least 4, to the third one at least 5. It sums up to 14, which is greater than 10 milliliters available.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's introduce some definitions that will be needed later.

Let $prime(x)$ be the set of prime divisors of $x$. For example, $prime(140) = \{ 2, 5, 7 \}$, $prime(169) = \{ 13 \}$.

Let $g(x, p)$ be the maximum possible integer $p^k$ where $k$ is an integer such that $x$ is divisible by $p^k$. For example:  $g(45, 3) = 9$ ($45$ is divisible by $3^2=9$ but not divisible by $3^3=27$),  $g(63, 7) = 7$ ($63$ is divisible by $7^1=7$ but not divisible by $7^2=49$). 

Let $f(x, y)$ be the product of $g(y, p)$ for all $p$ in $prime(x)$. For example:  $f(30, 70) = g(70, 2) \cdot g(70, 3) \cdot g(70, 5) = 2^1 \cdot 3^0 \cdot 5^1 = 10$,  $f(525, 63) = g(63, 3) \cdot g(63, 5) \cdot g(63, 7) = 3^2 \cdot 5^0 \cdot 7^1 = 63$. 

You have integers $x$ and $n$. Calculate $f(x, 1) \cdot f(x, 2) \cdot \ldots \cdot f(x, n) \bmod{(10^{9} + 7)}$.


-----Input-----

The only line contains integers $x$ and $n$ ($2 \le x \le 10^{9}$, $1 \le n \le 10^{18}$) — the numbers used in formula.


-----Output-----

Print the answer.


-----Examples-----
Input
10 2

Output
2

Input
20190929 1605

Output
363165664

Input
947 987654321987654321

Output
593574252



-----Note-----

In the first example, $f(10, 1) = g(1, 2) \cdot g(1, 5) = 1$, $f(10, 2) = g(2, 2) \cdot g(2, 5) = 2$.

In the second example, actual value of formula is approximately $1.597 \cdot 10^{171}$. Make sure you print the answer modulo $(10^{9} + 7)$.

In the third example, be careful about overflow issue.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Once upon a time in the Kingdom of Far Far Away lived Sir Lancelot, the chief Royal General. He was very proud of his men and he liked to invite the King to come and watch drill exercises which demonstrated the fighting techniques and tactics of the squad he was in charge of. But time went by and one day Sir Lancelot had a major argument with the Fairy Godmother (there were rumors that the argument occurred after the general spoke badly of the Godmother's flying techniques. That seemed to hurt the Fairy Godmother very deeply). 

As the result of the argument, the Godmother put a rather strange curse upon the general. It sounded all complicated and quite harmless: "If the squared distance between some two soldiers equals to 5, then those soldiers will conflict with each other!"

The drill exercises are held on a rectangular *n*<=×<=*m* field, split into *nm* square 1<=×<=1 segments for each soldier. Thus, the square of the distance between the soldiers that stand on squares (*x*1,<=*y*1) and (*x*2,<=*y*2) equals exactly (*x*1<=-<=*x*2)2<=+<=(*y*1<=-<=*y*2)2. Now not all *nm* squad soldiers can participate in the drill exercises as it was before the Fairy Godmother's curse. Unless, of course, the general wants the soldiers to fight with each other or even worse... For example, if he puts a soldier in the square (2,<=2), then he cannot put soldiers in the squares (1,<=4), (3,<=4), (4,<=1) and (4,<=3) — each of them will conflict with the soldier in the square (2,<=2).

Your task is to help the general. You are given the size of the drill exercise field. You are asked to calculate the maximum number of soldiers that can be simultaneously positioned on this field, so that no two soldiers fall under the Fairy Godmother's curse.

Input Specification:
The single line contains space-separated integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=1000) that represent the size of the drill exercise field.

Output Specification:
Print the desired maximum number of warriors.

Demo Input:
['2 4\n', '3 4\n']

Demo Output:
['4', '6']

Note:
In the first sample test Sir Lancelot can place his 4 soldiers on the 2 × 4 court as follows (the soldiers' locations are marked with gray circles on the scheme):

In the second sample test he can place 6 soldiers on the 3 × 4 site in the following manner:

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mike and some bears are playing a game just for fun. Mike is the judge. All bears except Mike are standing in an *n*<=×<=*m* grid, there's exactly one bear in each cell. We denote the bear standing in column number *j* of row number *i* by (*i*,<=*j*). Mike's hands are on his ears (since he's the judge) and each bear standing in the grid has hands either on his mouth or his eyes.

They play for *q* rounds. In each round, Mike chooses a bear (*i*,<=*j*) and tells him to change his state i. e. if his hands are on his mouth, then he'll put his hands on his eyes or he'll put his hands on his mouth otherwise. After that, Mike wants to know the score of the bears.

Score of the bears is the maximum over all rows of number of consecutive bears with hands on their eyes in that row.

Since bears are lazy, Mike asked you for help. For each round, tell him the score of these bears after changing the state of a bear selected in that round.

Input Specification:
The first line of input contains three integers *n*, *m* and *q* (1<=≤<=*n*,<=*m*<=≤<=500 and 1<=≤<=*q*<=≤<=5000).

The next *n* lines contain the grid description. There are *m* integers separated by spaces in each line. Each of these numbers is either 0 (for mouth) or 1 (for eyes).

The next *q* lines contain the information about the rounds. Each of them contains two integers *i* and *j* (1<=≤<=*i*<=≤<=*n* and 1<=≤<=*j*<=≤<=*m*), the row number and the column number of the bear changing his state.

Output Specification:
After each round, print the current score of the bears.

Demo Input:
['5 4 5\n0 1 1 0\n1 0 0 1\n0 1 1 0\n1 0 0 1\n0 0 0 0\n1 1\n1 4\n1 1\n4 2\n4 3\n']

Demo Output:
['3\n4\n3\n3\n4\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a spreadsheet that contains a list of $N$ athletes and their details (such as age, height, weight and so on). You are required to sort the data based on the $K^{th}$ attribute and print the final resulting table. Follow the example given below for better understanding. 

Note that $\mbox{K}$ is indexed from $\mbox{0}$ to $M-1$, where $\mbox{M}$ is the number of attributes. 

Note: If two attributes are the same for different rows, for example, if two atheletes are of the same age, print the row that appeared first in the input.

Input Format

The first line contains $N$ and $\mbox{M}$ separated by a space. 

The next $N$ lines each contain $\mbox{M}$ elements. 

The last line contains $\mbox{K}$.     

Constraints

$1\leq N,M\leq1000$ 

$0\leq K<M$ 

Each element $\leq1000$

Output Format

Print the $N$ lines of the sorted table. Each line should contain the space separated elements. Check the sample below for clarity.   

Sample Input 0
5 3
10 2 5
7 1 0
9 9 9
1 23 12
6 5 9
1

Sample Output 0
7 1 0
10 2 5
6 5 9
9 9 9
1 23 12

Explanation 0

The details are sorted based on the second attribute, since $\mbox{K}$ is zero-indexed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose there is a X x Y x Z 3D matrix A of numbers having coordinates (i, j, k) where 0 ≤ i < X, 0 ≤ j < Y, 0 ≤ k < Z. Now another X x Y x Z matrix B is defined from A such that the (i, j, k) element of B is the sum of all the the numbers in A in the cuboid defined by the (0, 0, 0) and (i, j, k) elements as the diagonally opposite vertices. In other word (i, j, k) in B is the sum of numbers of A having coordinates (a, b, c) such that 0 ≤ a ≤ i, 0 ≤ b ≤ j, 0 ≤ c ≤ k. The problem is that given B, you have to find out A.

-----Input-----
The first line of input will contain the number of test cases ( ≤ 10). That many test cases will follow in subsequent lines. The first line of each test case will contain the numbers X Y Z (0 ≤ X, Y, Z ≤ 100). After that there will be X x Y lines each containing Z numbers of B. The first line contains the numbers (0, 0, 0), (0, 0, 1)..., (0, 0, Z-1). The second line has the numbers (0, 1, 0), (0, 1, 1)..., (0, 1, Z-1) and so on. The (Y+1)th line will have the numbers (1, 0, 0), (1, 0, 1)..., (1, 0, Z-1) and so on.

-----Output-----
For each test case print the numbers of A in exactly the same fashion as the input.

-----Example-----
Input:
2
3 1 1
1 
8 
22 
1 2 3
0 9 13 
18 45 51 

Output:
1 
7 
14 
0 9 4 
18 18 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sengoku still remembers the mysterious "colourful meteoroids" she discovered with Lala-chan when they were little. In particular, one of the nights impressed her deeply, giving her the illusion that all her fancies would be realized.

On that night, Sengoku constructed a permutation p_1, p_2, ..., p_{n} of integers from 1 to n inclusive, with each integer representing a colour, wishing for the colours to see in the coming meteor outburst. Two incredible outbursts then arrived, each with n meteorids, colours of which being integer sequences a_1, a_2, ..., a_{n} and b_1, b_2, ..., b_{n} respectively. Meteoroids' colours were also between 1 and n inclusive, and the two sequences were not identical, that is, at least one i (1 ≤ i ≤ n) exists, such that a_{i} ≠ b_{i} holds.

Well, she almost had it all — each of the sequences a and b matched exactly n - 1 elements in Sengoku's permutation. In other words, there is exactly one i (1 ≤ i ≤ n) such that a_{i} ≠ p_{i}, and exactly one j (1 ≤ j ≤ n) such that b_{j} ≠ p_{j}.

For now, Sengoku is able to recover the actual colour sequences a and b through astronomical records, but her wishes have been long forgotten. You are to reconstruct any possible permutation Sengoku could have had on that night.


-----Input-----

The first line of input contains a positive integer n (2 ≤ n ≤ 1 000) — the length of Sengoku's permutation, being the length of both meteor outbursts at the same time.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ n) — the sequence of colours in the first meteor outburst.

The third line contains n space-separated integers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ n) — the sequence of colours in the second meteor outburst. At least one i (1 ≤ i ≤ n) exists, such that a_{i} ≠ b_{i} holds.


-----Output-----

Output n space-separated integers p_1, p_2, ..., p_{n}, denoting a possible permutation Sengoku could have had. If there are more than one possible answer, output any one of them.

Input guarantees that such permutation exists.


-----Examples-----
Input
5
1 2 3 4 3
1 2 5 4 5

Output
1 2 5 4 3

Input
5
4 4 2 3 1
5 4 5 3 1

Output
5 4 2 3 1

Input
4
1 1 3 4
1 4 3 4

Output
1 2 3 4



-----Note-----

In the first sample, both 1, 2, 5, 4, 3 and 1, 2, 3, 4, 5 are acceptable outputs.

In the second sample, 5, 4, 2, 3, 1 is the only permutation to satisfy the constraints.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your wizard cousin works at a Quidditch stadium and wants you to write a function that calculates the points for the Quidditch scoreboard! 

# Story

Quidditch is a sport with two teams. The teams score goals by throwing the Quaffle through a hoop, each goal is worth **10 points**.

The referee also deducts 30 points (**- 30 points**) from the team who are guilty of carrying out any of these fouls: Blatching, Blurting, Bumphing, Haverstacking, Quaffle-pocking, Stooging 

The match is concluded when the Snitch is caught, and catching the Snitch is worth **150 points**. Let's say a Quaffle goes through the hoop just seconds after the Snitch is caught, in that case the points of that goal should not end up on the scoreboard seeing as the match is already concluded. 

You don't need any prior knowledge of how Quidditch works in order to complete this kata, but if you want to read up on what it is, here's a link: https://en.wikipedia.org/wiki/Quidditch

# Task

You will be given a string with two arguments, the first argument will tell you which teams are playing and the second argument tells you what's happened in the match. Calculate the points and return a string containing the teams final scores, with the team names sorted in the same order as in the first argument. 

# Examples:

# Given an input of:

# The expected output would be:

Separate the team names from their respective points with a colon and separate the two teams with a comma. 

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is again playing a game with his best friend Garry. As usual, the rules of this game are extremely strange and uncommon.
First, they are given a stack of $N$ discs. Each disc has a distinct, non-negative integer written on it. The players exchange turns to make a move. Before the start of the game, they both agree upon a set of positive integers  $S$ of size $K$. It is guaranteed that S contains the integer $1$. In a move, a player can select any value $x$ from $S$ and pop exactly $x$ elements from the top of the stack. The game ends when there are no discs remaining. Chef goes first.
Scoring: For every disc a player pops, his score increases by $2^p$ where $p$ is the integer written on the disc. For example, if a player pops the discs, with integers $p_1, p_2, p_3, \dots, p_m$ written on it, during the entire course of the game, then his total score will be $2^{p_1} + 2^{p_2} + 2^{p_3} + \dots + 2^{p_m}$.
The player with higher score wins the game. Determine the winner if both the players play optimally, or if the game ends in a draw.

-----Input:-----
- First line contains $T$, the number of testcases. Then the testcases follow.
- The first line of each test case contains two space separated integers $N$ and $K$, denoting the size of the stack and the set S respectively.
- Next line contains $N$ space separated integers $A_i$ where $A_1$ is the topmost element, denoting the initial arrangement of the stack.
- The last line of each test case contains $K$ space separated integers each denoting $x_i$.

-----Output:-----
For each testcase, output "Chef" (without quotes) if Chef wins, "Garry" (without quotes) if Garry wins, otherwise "Draw" (without quotes) in a separate line.

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq N \leq 10^5$
- $1 \leq K \leq \min(100, N)$
- $0 \leq A_i \leq 10^9$
- $1 \leq x_i \leq N$
- $x_i \neq x_j$ for all $i \neq j$
- $A_i \neq A_j$ for all $i \neq j$
- Set $S$ contains integer $1$. 
- Sum of $N$ over all test cases does not exceed $10^5$.

-----Sample Input:-----
1
3 2
5 7 1
1 2

-----Sample Output:-----
Chef

-----Explanation:-----
Chef can select 2 from the set and draw the top two discs (with integers 5 and 7 written on it) from the stack. Garry cannot select 2 from the set as there is only 1 disc left in the stack. However, he can select 1 from the set and pop the last disc.
So, Chef's score = $2^5$ + $2^7$ = $160$

Garry's score = $2^1$ = $2$

Chef wins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yaroslav calls an array of r integers a1, a2, ..., ar good, if it meets the following conditions: |a1 - a2| = 1, |a2 - a3| = 1, ..., |ar - 1 - ar| = 1, |ar - a1| = 1, at that <image>. 

An array of integers b1, b2, ..., br is called great, if it meets the following conditions:

  1. The elements in it do not decrease (bi ≤ bi + 1). 
  2. If the inequalities 1 ≤ r ≤ n and 1 ≤ bi ≤ m hold. 
  3. If we can rearrange its elements and get at least one and at most k distinct good arrays. 



Yaroslav has three integers n, m, k. He needs to count the number of distinct great arrays. Help Yaroslav! As the answer may be rather large, print the remainder after dividing it by 1000000007 (109 + 7).

Two arrays are considered distinct if there is a position in which they have distinct numbers.

Input

The single line contains three integers n, m, k (1 ≤ n, m, k ≤ 100).

Output

In a single line print the remainder after dividing the answer to the problem by number 1000000007 (109 + 7).

Examples

Input

1 1 1


Output

0


Input

3 3 3


Output

2

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