vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The Chef has been hunting for a machine developed to change numbers in a rather peculiar manner. This machine has a fixed number c associated with it and a changing number X. 

In a single step, the Chef can do the following:
First, choose any positive integer b that is a perfect c-th power of some number (that is, there is some positive integer n such that b = n^{c})
Then, change X \to \dfrac{\text{lcm}(b, X)}{\gcd(b, X)}

He wants to find the minimum number he can change X into by applying these operations alone any number of times (possibly none at all). However, he does not know the exact values of X, c for the machine, but he does have T guesses for what these values might be. For each of these guesses, compute the minimum number Chef can obtain.

------ Input Format ------ 

- The first line of input will contain an integer T, the number of guesses Chef has for the pair (X, c). Then the guesses follow.
- Each guess consists of a single line of input containing two space-separated integers X, c.

------ Output Format ------ 

For each guess, print on a new line the minimum value that Chef can change X into by applying any number of operations (possibly none at all).

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

$1 ≤ T ≤ 100$
$1 ≤ X ≤ 10^{10}$
$1 ≤ c ≤ 30$

----- Sample Input 1 ------ 
3
1 5
10 1
20 4
----- Sample Output 1 ------ 
1
1
20
----- explanation 1 ------ 
Guess $1$: It can easily be checked that $X = 1$ cannot be changed.

Guess $2$: Choose $b = 10^{1}$ and change $X : 10 \to \dfrac{\text{lcm}(10, 10)}{\gcd(10, 10)} = 1$. This is the minimum possible value of $X$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today is Chef's birthday. His mom gifted him a truly lovable gift, a permutation of first N positive integers.
She placed the permutation on a very long table in front of Chef and left it for him to play with it. But as there was a lot of people coming and wishing him. It was interfering with his game which made him very angry and he banged the table very hard due to which K numbers from the permutation fell down and went missing.
Seeing her son's gift being spoilt, his mom became very sad. Chef didn't want his mom to be sad as he loves her the most. So to make her happy, he decided to play a game with her with the remaining N - K numbers on the table. Chef wants his mom to win all the games.
Chef and his mom play alternatively and optimally. In Xth move, a player can choose some numbers out of all the numbers available on the table such that chosen numbers sum up to X. After the move, Chosen numbers are placed back on the table.The player who is not able to make a move loses.
Now, Chef has to decide who should move first so that his Mom wins the game.
As Chef is a small child, he needs your help to decide who should move first. Please help him, he has promised to share his birthday cake with you :)

Input

First Line of input contains a single integer T denoting the number of test cases. 
First line of each test case contains two space separated integers N and K denoting the size of
 permutation and number of numbers fall down from the table. 
Next line of each test case contains K space separated integers denoting the values of missing numbers.


Output
For each test case, print "Chef" if chef should move first otherwise print "Mom" (without quotes).

Constraints

 1 ≤ T ≤ 10^5, 1 ≤ N ≤ 10^9
0 ≤ K ≤ min(10^5, N)
All K numbers are distinct.
Value of each of K number belongs to [1,N].
Sum of K over all the test cases does not exceed 5*10^5.


Scoring

Example

Input
2
5 2
3 5
5 1
1
Output
Mom
Chef

Explanation
For test case 1.

 Mom can choose {1} to make 1.
 Chef can choose {2} to make 2.
 Mom can choose {1,2} to make 3.
 Chef can choose {4} to make 4.
 Mom can choose {1,4} to make 5.
 Chef can choose {2,4} to make 6.
 Mom can choose {1,2,4} to make 7.
 Chef cannot make 8 out of the numbers on the table.

 So,Chef loses and Mom wins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a directed graph consisting of n vertices and m edges (each edge is directed, so it can be traversed in only one direction). You are allowed to remove at most one edge from it.

Can you make this graph acyclic by removing at most one edge from it? A directed graph is called acyclic iff it doesn't contain any cycle (a non-empty path that starts and ends in the same vertex).


-----Input-----

The first line contains two integers n and m (2 ≤ n ≤ 500, 1 ≤ m ≤ min(n(n - 1), 100000)) — the number of vertices and the number of edges, respectively.

Then m lines follow. Each line contains two integers u and v denoting a directed edge going from vertex u to vertex v (1 ≤ u, v ≤ n, u ≠ v). Each ordered pair (u, v) is listed at most once (there is at most one directed edge from u to v).


-----Output-----

If it is possible to make this graph acyclic by removing at most one edge, print YES. Otherwise, print NO.


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

Output
YES

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

Output
NO



-----Note-----

In the first example you can remove edge $2 \rightarrow 3$, and the graph becomes acyclic.

In the second example you have to remove at least two edges (for example, $2 \rightarrow 1$ and $2 \rightarrow 3$) in order to make the graph acyclic.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Johnny was asked by his math teacher to compute nn (n to the power of n, where n is an integer), and has to read his answer out loud. This is a bit of a tiring task, since the result is probably an extremely large number, and would certainly keep Johnny occupied for a while if he were to do it honestly. But Johnny knows that the teacher will certainly get bored when listening to his answer, and will sleep through most of it! So, Johnny feels he will get away with reading only the first k digits of the result before the teacher falls asleep, and then the last k digits when the teacher wakes up.

Write a program to help Johnny to compute the digits he will need to read out.

-----Input-----
The first line contains t, the number of test cases (about 30000). Then t test cases follow.
Each test case consists of one line containing two numbers n and k (1 ≤ n ≤ 109, 1 ≤ k ≤ 9). It is guaranteed that k is not more than the number of digits of nn.

-----Output-----
For each test case, print out one line containing two numbers, separated by a space, which are the first and the last k digits of nn.

-----Example-----
Input
2
4 2
9 3

Output
25 56
387 489

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A very brave explorer Petya once decided to explore Paris catacombs. Since Petya is not really experienced, his exploration is just walking through the catacombs.

Catacombs consist of several rooms and bidirectional passages between some pairs of them. Some passages can connect a room to itself and since the passages are built on different depths they do not intersect each other. Every minute Petya arbitrary chooses a passage from the room he is currently in and then reaches the room on the other end of the passage in exactly one minute. When he enters a room at minute *i*, he makes a note in his logbook with number *t**i*: 
 -  If Petya has visited this room before, he writes down the minute he was in this room last time; -  Otherwise, Petya writes down an arbitrary non-negative integer strictly less than current minute *i*. 
Initially, Petya was in one of the rooms at minute 0, he didn't write down number *t*0.

At some point during his wandering Petya got tired, threw out his logbook and went home. Vasya found his logbook and now he is curious: what is the minimum possible number of rooms in Paris catacombs according to Petya's logbook?

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=2·105) — then number of notes in Petya's logbook.

The second line contains *n* non-negative integers *t*1,<=*t*2,<=...,<=*t**n* (0<=≤<=*t**i*<=&lt;<=*i*) — notes in the logbook.

Output Specification:
In the only line print a single integer — the minimum possible number of rooms in Paris catacombs.

Demo Input:
['2\n0 0\n', '5\n0 1 0 1 3\n']

Demo Output:
['2\n', '3\n']

Note:
In the first sample, sequence of rooms Petya visited could be, for example 1 → 1 → 2, 1 → 2 → 1 or 1 → 2 → 3. The minimum possible number of rooms is 2.

In the second sample, the sequence could be 1 → 2 → 3 → 1 → 2 → 1.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are $n$ rectangles in a row. You can either turn each rectangle by $90$ degrees or leave it as it is. If you turn a rectangle, its width will be height, and its height will be width. Notice that you can turn any number of rectangles, you also can turn all or none of them. You can not change the order of the rectangles.

Find out if there is a way to make the rectangles go in order of non-ascending height. In other words, after all the turns, a height of every rectangle has to be not greater than the height of the previous rectangle (if it is such).

Input Specification:
The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of rectangles.

Each of the next $n$ lines contains two integers $w_i$ and $h_i$ ($1 \leq w_i, h_i \leq 10^9$) — the width and the height of the $i$-th rectangle.

Output Specification:
Print "YES" (without quotes) if there is a way to make the rectangles go in order of non-ascending height, otherwise print "NO".

You can print each letter in any case (upper or lower).

Demo Input:
['3\n3 4\n4 6\n3 5\n', '2\n3 4\n5 5\n']

Demo Output:
['YES\n', 'NO\n']

Note:
In the first test, you can rotate the second and the third rectangles so that the heights will be [4, 4, 3].

In the second test, there is no way the second rectangle will be not higher than the first one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a single 3D printer, and would like to use it to produce $n$ statues. However, printing the statues one by one on the 3D printer takes a long time, so it may be more time-efficient to first use the 3D printer to print a new printer. That new printer may then in turn be used to print statues or even more printers. Print jobs take a full day, and every day you can choose for each printer in your possession to have it print a statue, or to have it 3D print a new printer (which becomes available for use the next day).

What is the minimum possible number of days needed to print at least $n$ statues?

-----Input-----
The input contains a single integer $n$ ($1 \le n \le 10000$), the number of statues you need to print.

-----Output-----
Output a single integer, the minimum number of days needed to print at least $n$ statues.

-----Examples-----
Sample Input:
1
Sample Output:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polygon is not only the best platform for developing problems but also a square matrix with side $n$, initially filled with the character 0.

On the polygon, military training was held. The soldiers placed a cannon above each cell in the first row and a cannon to the left of each cell in the first column. Thus, exactly $2n$ cannons were placed. [Image] Initial polygon for $n=4$. 

Cannons shoot character 1. At any moment of time, no more than one cannon is shooting. When a 1 flies out of a cannon, it flies forward (in the direction of the shot) until it collides with a polygon border or another 1. After that, it takes the cell in which it was before the collision and remains there. Take a look at the examples for better understanding.

More formally:   if a cannon stands in the row $i$, to the left of the first column, and shoots with a 1, then the 1 starts its flight from the cell ($i, 1$) and ends in some cell ($i, j$);  if a cannon stands in the column $j$, above the first row, and shoots with a 1, then the 1 starts its flight from the cell ($1, j$) and ends in some cell ($i, j$). 

For example, consider the following sequence of shots: [Image] 

 1. Shoot the cannon in the row $2$.                         2. Shoot the cannon in the row $2$.                         3. Shoot the cannon in column $3$. 

You have a report from the military training on your desk. This report is a square matrix with side length $n$ consisting of 0 and 1. You wonder if the training actually happened. In other words, is there a sequence of shots such that, after the training, you get the given matrix?

Each cannon can make an arbitrary number of shots. Before the training, each cell of the polygon contains 0.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow.

Each test case starts with a line containing an integer $n$ ($1 \le n \le 50$) — the size of the polygon.

This is followed by $n$ lines of length $n$, consisting of 0 and 1 — the polygon matrix after the training.

The total area of the matrices in all test cases in one test does not exceed $10^5$.


-----Output-----

For each test case print:  YES if there is a sequence of shots leading to a given matrix;  NO if such a sequence does not exist. 

The letters in the words YES and NO can be printed in any case.


-----Example-----
Input
5
4
0010
0011
0000
0000
2
10
01
2
00
00
4
0101
1111
0101
0111
4
0100
1110
0101
0111

Output
YES
NO
YES
YES
NO



-----Note-----

The first test case was explained in the statement.

The answer to the second test case is NO, since a 1 in a cell ($1, 1$) flying out of any cannon would continue its flight further.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* beacons located at distinct positions on a number line. The *i*-th beacon has position *a**i* and power level *b**i*. When the *i*-th beacon is activated, it destroys all beacons to its left (direction of decreasing coordinates) within distance *b**i* inclusive. The beacon itself is not destroyed however. Saitama will activate the beacons one at a time from right to left. If a beacon is destroyed, it cannot be activated.

Saitama wants Genos to add a beacon strictly to the right of all the existing beacons, with any position and any power level, such that the least possible number of beacons are destroyed. Note that Genos's placement of the beacon means it will be the first beacon activated. Help Genos by finding the minimum number of beacons that could be destroyed.

Input Specification:
The first line of input contains a single integer *n* (1<=≤<=*n*<=≤<=100<=000) — the initial number of beacons.

The *i*-th of next *n* lines contains two integers *a**i* and *b**i* (0<=≤<=*a**i*<=≤<=1<=000<=000, 1<=≤<=*b**i*<=≤<=1<=000<=000) — the position and power level of the *i*-th beacon respectively. No two beacons will have the same position, so *a**i*<=≠<=*a**j* if *i*<=≠<=*j*.

Output Specification:
Print a single integer — the minimum number of beacons that could be destroyed if exactly one beacon is added.

Demo Input:
['4\n1 9\n3 1\n6 1\n7 4\n', '7\n1 1\n2 1\n3 1\n4 1\n5 1\n6 1\n7 1\n']

Demo Output:
['1\n', '3\n']

Note:
For the first sample case, the minimum number of beacons destroyed is 1. One way to achieve this is to place a beacon at position 9 with power level 2.

For the second sample case, the minimum number of beacons destroyed is 3. One way to achieve this is to place a beacon at position 1337 with power level 42.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice, the president of club FCB, wants to build a team for the new volleyball tournament. The team should consist of p players playing in p different positions. She also recognizes the importance of audience support, so she wants to select k people as part of the audience.

There are n people in Byteland. Alice needs to select exactly p players, one for each position, and exactly k members of the audience from this pool of n people. Her ultimate goal is to maximize the total strength of the club.

The i-th of the n persons has an integer a_{i} associated with him — the strength he adds to the club if he is selected as a member of the audience.

For each person i and for each position j, Alice knows s_{i, j} — the strength added by the i-th person to the club if he is selected to play in the j-th position.

Each person can be selected at most once as a player or a member of the audience. You have to choose exactly one player for each position.

Since Alice is busy, she needs you to help her find the maximum possible strength of the club that can be achieved by an optimal choice of players and the audience.

Input

The first line contains 3 integers n,p,k (2 ≤ n ≤ 10^{5}, 1 ≤ p ≤ 7, 1 ≤ k, p+k ≤ n).

The second line contains n integers a_{1},a_{2},…,a_{n}. (1 ≤ a_{i} ≤ 10^{9}).

The i-th of the next n lines contains p integers s_{i, 1}, s_{i, 2}, ..., s_{i, p}. (1 ≤ s_{i,j} ≤ 10^{9})

Output

Print a single integer {res} — the maximum possible strength of the club.

Examples

Input


4 1 2
1 16 10 3
18
19
13
15


Output


44


Input


6 2 3
78 93 9 17 13 78
80 97
30 52
26 17
56 68
60 36
84 55


Output


377


Input


3 2 1
500 498 564
100002 3
422332 2
232323 1


Output


422899

Note

In the first sample, we can select person 1 to play in the 1-st position and persons 2 and 3 as audience members. Then the total strength of the club will be equal to a_{2}+a_{3}+s_{1,1}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anton loves transforming one permutation into another one by swapping elements for money, and Ira doesn't like paying for stupid games. Help them obtain the required permutation by paying as little money as possible.

More formally, we have two permutations, p and s of numbers from 1 to n. We can swap p_{i} and p_{j}, by paying |i - j| coins for it. Find and print the smallest number of coins required to obtain permutation s from permutation p. Also print the sequence of swap operations at which we obtain a solution. 


-----Input-----

The first line contains a single number n (1 ≤ n ≤ 2000) — the length of the permutations.

The second line contains a sequence of n numbers from 1 to n — permutation p. Each number from 1 to n occurs exactly once in this line.

The third line contains a sequence of n numbers from 1 to n — permutation s. Each number from 1 to n occurs once in this line.


-----Output-----

In the first line print the minimum number of coins that you need to spend to transform permutation p into permutation s.

In the second line print number k (0 ≤ k ≤ 2·10^6) — the number of operations needed to get the solution.

In the next k lines print the operations. Each line must contain two numbers i and j (1 ≤ i, j ≤ n, i ≠ j), which means that you need to swap p_{i} and p_{j}.

It is guaranteed that the solution exists.


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

Output
3
2
4 3
3 1



-----Note-----

In the first sample test we swap numbers on positions 3 and 4 and permutation p becomes 4 2 3 1. We pay |3 - 4| = 1 coins for that. On second turn we swap numbers on positions 1 and 3 and get permutation 3241 equal to s. We pay |3 - 1| = 2 coins for that. In total we pay three coins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer n. The problem is to check whether only the first and last bits are set in the binary representation of n. The answer is 1 if the first and last bit is set else 0.
Example 1:
Input: N = 9
Output: 1
Explanation: (9)_{10} = (1001)_{2}, only 
the first and last bits are set.
â€‹Example 2:
Input: N = 15
Output: 0
Explanation: (15)_{10} = (1111)_{2}, except 
first and last there are other bits also
which are set.
Your Task:  
Your task is to complete the function onlyFirstAndLastAreSet() which takes the N as inputs and returns the answer.
Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{9}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a rectangular grid of n rows of m initially-white cells each.

Arkady performed a certain number (possibly zero) of operations on it. In the i-th operation, a non-empty subset of rows R_{i} and a non-empty subset of columns C_{i} are chosen. For each row r in R_{i} and each column c in C_{i}, the intersection of row r and column c is coloured black.

There's another constraint: a row or a column can only be chosen at most once among all operations. In other words, it means that no pair of (i, j) (i < j) exists such that $R_{i} \cap R_{j} \neq \varnothing$ or $C_{i} \cap C_{j} \neq \varnothing$, where [Image] denotes intersection of sets, and $\varnothing$ denotes the empty set.

You are to determine whether a valid sequence of operations exists that produces a given final grid.


-----Input-----

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 50) — the number of rows and columns of the grid, respectively.

Each of the following n lines contains a string of m characters, each being either '.' (denoting a white cell) or '#' (denoting a black cell), representing the desired setup.


-----Output-----

If the given grid can be achieved by any valid sequence of operations, output "Yes"; otherwise output "No" (both without quotes).

You can print each character in any case (upper or lower).


-----Examples-----
Input
5 8
.#.#..#.
.....#..
.#.#..#.
#.#....#
.....#..

Output
Yes

Input
5 5
..#..
..#..
#####
..#..
..#..

Output
No

Input
5 9
........#
#........
..##.#...
.......#.
....#.#.#

Output
No



-----Note-----

For the first example, the desired setup can be produced by 3 operations, as is shown below.

 [Image] 

For the second example, the desired setup cannot be produced, since in order to colour the center row, the third row and all columns must be selected in one operation, but after that no column can be selected again, hence it won't be possible to colour the other cells in the center column.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
According to rules of the Berland fashion, a jacket should be fastened by all the buttons except only one, but not necessarily it should be the last one. Also if the jacket has only one button, it should be fastened, so the jacket will not swinging open.

You are given a jacket with n buttons. Determine if it is fastened in a right way.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 1000) — the number of buttons on the jacket.

The second line contains n integers a_{i} (0 ≤ a_{i} ≤ 1). The number a_{i} = 0 if the i-th button is not fastened. Otherwise a_{i} = 1.


-----Output-----

In the only line print the word "YES" if the jacket is fastened in a right way. Otherwise print the word "NO".


-----Examples-----
Input
3
1 0 1

Output
YES

Input
3
1 0 0

Output
NO

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