vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Vasya and Beautiful Arrays

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya's got a birthday coming up and his mom decided to give him an array of positive integers *a* of length *n*.

Vasya thinks that an array's beauty is the greatest common divisor of all its elements. His mom, of course, wants to give him as beautiful an array as possible (with largest possible beauty). Unfortunately, the shop has only one array *a* left. On the plus side, the seller said that he could decrease some numbers in the array (no more than by *k* for each number).

The seller can obtain array *b* from array *a* if the following conditions hold: *b**i*<=&gt;<=0; 0<=≤<=*a**i*<=-<=*b**i*<=≤<=*k* for all 1<=≤<=*i*<=≤<=*n*.

Help mom find the maximum possible beauty of the array she will give to Vasya (that seller can obtain).

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*<=≤<=3·105;<=1<=≤<=*k*<=≤<=106). The second line contains *n* integers *a**i* (1<=≤<=*a**i*<=≤<=106) — array *a*.

Output Specification:
In the single line print a single number — the maximum possible beauty of the resulting array.

Demo Input:
['6 1\n3 6 10 12 13 16\n', '5 3\n8 21 52 15 77\n']

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

Note:
In the first sample we can obtain the array:

3 6 9 12 12 15

In the second sample we can obtain the next array:

7 21 49 14 77

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
`This kata is the first of the ADFGX Ciphers, the harder version can be found `here.

The ADFGX Cipher is a pretty well-known Cryptographic tool, and is essentially a modified Polybius Square.

Rather than having numbers as coordinates on the table, it has the letters:

 `A, D, F, G, X`

Also, because this is the first step, and to help simplify things, you won't have to worry about a key, or the corresponding columnar transposition. In this kata ;)

All you have to do is encrypt and decrypt a string into `ADFGX` format.

`adfgx_encrypt() and adfgx_decrypt()` will be passed a string, `plaintext` and `ciphertext` respectively, and an adfgx`square`, for which will guide the operations. 

Now for some examples to clear confusion:

```python
adfgx_encrypt("helloworld", "bchigklnmoqprstuvwxyzadef")

    A D F G X
   
A   b c h i g
D   k l n m o     
F   q p r s t  -> square (PLEASE NOTE, j SHOULD BE TREATED AS i)  
G   u v w x y  
X   z a d e f

"helloworld"   -> plaintext

EVALUATES TO:

      F  
          -> "AF"
A     h
--------------
          G 
               -> "XG"  
X         e 

AND SO FORTH...

#Results in:

adfgx_encrypt("helloworld", "bchigklnmoqprstuvwxyzadef") 
==
"AFXGDDDDDXGFDXFFDDXF"
```
Now decryption:
```python
adfgx_decrypt("FGXGADGDXGFXAXXGFGFGAADGXG", "aczlmuqngoipvstkrwfxhdbey) 

    A D F G X

A   a c z l m
D   u q n g o     
F   i p v s t  -> square (PLEASE NOTE, j SHOULD BE TREATED AS i)  
G   k r w f x  
X   h d b e y

"FGXGADGDXGFXAXXGFGFGAADGXG"   -> ciphertext

"FG" == "s"
"XG" == "e"

AND SO ON:

adfgx_decrypt("FGXGADGDXGFXAXXGFGFGAADGXG", "aczlmuqngoipvstkrwfxhdbey) 
==
"secretmessage"
```
PLEASE NOTE: ALL INPUT WILL BE VALID, NO NEED TO ERROR CHECK :D

What are you waiting for?!
Go create `adfgx_encrypt() and adfgx_decrypt()`!

Good Luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lukáš loves skiing. One morning, the sun was shining like no other sun had ever shone before, and he wanted to do something exciting. There had been a slight storm during the night, and the wind had cleared snow from certain parts of the mountain, making them icy and more dangerous to ski down. Lukáš was aware of this, but brave as he (mostly) is, he decided that he would climb his favourite mountain and go for some really exciting skiing. 

Lukáš starts at the top of the mountain, and wants to get to the bottom. There are $N$ small cabins scattered along the mountainside, numbered $0$ to $N-1$. He will always go from one cabin to another, along certain pistes. For each piste, which always connects exactly two cabins, he has calculated the probability of falling along that piste. The cabin numbered $0$ is located at the top, and the cabin numbered $N-1$ is located at the bottom of the mountain.

If Lukáš feels like it, he can take his skis off and walk down a piste instead. By doing this, it is guaranteed that he will not fall along this piste in the direction that he walks. But taking the skis off is not very brave…

Lukáš can only ski down the mountain, i.e. from a lower numbered cabin to a higher numbered one, but he can walk along any piste in any direction. It is guaranteed that Lukáš can walk from the top of the mountain to the bottom of it.

Your task is to help Lukáš predict his chances of getting down the hill without falling. For each number $k \in [0,N-1]$ you should calculate the maximum probability that Lukáš gets down the hill without falling, while walking along at most $k$ pistes, and assuming he choses his walking wisely.

-----Input-----
The first line contains two integers $1 \le N \le 300$ and $0 \le M \le \frac{N(N-1)}{2}$, the number of cabins and pistes respectively.

Then follow $M$ lines, each describing a piste with three numbers $0 \le a, b < N$ and $0 \le w \le 1$, where $a$ and $b$ are the numbers of the cabins the piste connects, and $w$ is the probability that Lukáš will fall while skiing down the piste.

-----Output-----
Output should consist of $N$ floating point numbers $p_ k$ ($k \in [0,N-1]$), each denoting the maximum probability that Lukáš didn’t fall when walking along at most $k$ pistes. If it is impossible to get down the hill by walking along at most $k$ pistes, then output $p_ k=-1$. Output them on a single line separated by spaces. Your answer is considered correct if the relative or absolute error is at most $10^{-9}$.

-----Examples-----
Sample Input:
2 1
0 1 0.5
Sample Output:
0.500000000 1.000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mike and Ann are sitting in the classroom. The lesson is boring, so they decided to play an interesting game. Fortunately, all they need to play this game is a string $s$ and a number $k$ ($0 \le k < |s|$).

At the beginning of the game, players are given a substring of $s$ with left border $l$ and right border $r$, both equal to $k$ (i.e. initially $l=r=k$). Then players start to make moves one by one, according to the following rules: A player chooses $l^{\prime}$ and $r^{\prime}$ so that $l^{\prime} \le l$, $r^{\prime} \ge r$ and $s[l^{\prime}, r^{\prime}]$ is lexicographically less than $s[l, r]$. Then the player changes $l$ and $r$ in this way: $l := l^{\prime}$, $r := r^{\prime}$. Ann moves first. The player, that can't make a move loses.

Recall that a substring $s[l, r]$ ($l \le r$) of a string $s$ is a continuous segment of letters from s that starts at position $l$ and ends at position $r$. For example, "ehn" is a substring ($s[3, 5]$) of "aaaehnsvz" and "ahz" is not.

Mike and Ann were playing so enthusiastically that they did not notice the teacher approached them. Surprisingly, the teacher didn't scold them, instead of that he said, that he can figure out the winner of the game before it starts, even if he knows only $s$ and $k$.

Unfortunately, Mike and Ann are not so keen in the game theory, so they ask you to write a program, that takes $s$ and determines the winner for all possible $k$.


-----Input-----

The first line of the input contains a single string $s$ ($1 \leq |s| \leq 5 \cdot 10^5$) consisting of lowercase English letters.


-----Output-----

Print $|s|$ lines.

In the line $i$ write the name of the winner (print Mike or Ann) in the game with string $s$ and $k = i$, if both play optimally


-----Examples-----
Input
abba

Output
Mike
Ann
Ann
Mike

Input
cba

Output
Mike
Mike
Mike

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array a consisting of n elements. You may apply several operations (possibly zero) to it.

During each operation, you choose two indices i and j (1 ≤ i, j ≤ n; i ≠ j), increase a_j by a_i, and remove the i-th element from the array (so the indices of all elements to the right to it decrease by 1, and n also decreases by 1).

Your goal is to make the array a strictly ascending. That is, the condition a_1 < a_2 < ... < a_n should hold (where n is the resulting size of the array).

Calculate the minimum number of actions required to make the array strictly ascending.

Input

The first line contains one integer T (1 ≤ T ≤ 10000) — the number of test cases.

Each test case consists of two lines. The first line contains one integer n (1 ≤ n ≤ 15) — the number of elements in the initial array a.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^6).

It is guaranteed that: 

  * the number of test cases having n ≥ 5 is not greater than 5000; 
  * the number of test cases having n ≥ 8 is not greater than 500; 
  * the number of test cases having n ≥ 10 is not greater than 100; 
  * the number of test cases having n ≥ 11 is not greater than 50; 
  * the number of test cases having n ≥ 12 is not greater than 25; 
  * the number of test cases having n ≥ 13 is not greater than 10; 
  * the number of test cases having n ≥ 14 is not greater than 3; 
  * the number of test cases having n ≥ 15 is not greater than 1. 

Output

For each test case, print the answer as follows:

In the first line, print k — the minimum number of operations you have to perform. Then print k lines, each containing two indices i and j for the corresponding operation. Note that the numeration of elements in the array changes after removing elements from it. If there are multiple optimal sequences of operations, print any one of them.

Example

Input


4
8
2 1 3 5 1 2 4 5
15
16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1
2
3 3
14
1 2 3 4 5 6 7 8 9 10 11 12 13 14


Output


3
6 8
1 6
4 1
7
1 15
1 13
1 11
1 9
1 7
1 5
1 3
1
2 1
0

Note

In the first test case, the sequence of operations changes a as follows:

[2, 1, 3, 5, 1, 2, 4, 5] → [2, 1, 3, 5, 1, 4, 7] → [1, 3, 5, 1, 6, 7] → [2, 3, 5, 6, 7].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Problem Statement:Captain America and Iron Man are at WAR and the rage inside Iron Man is rising.

But Iron Man faces a problem to identify the location of Captain America.

There are N buildings situtaed adjacently to each other and Captain America can be at any building.

Iron Man has to arrange the Buildings from 1 to N is such a way that Value(i.e abs(Building Number -Position of Building))=K for every building.

Can You help Iron Man to Find The Arrangement of the Buildings?

P.S- If no arrangement exist, then print         
“CAPTAIN AMERICA EVADES”.

Input Format:
The first line of input contains a single integer,T, denoting the number of test cases.

Each of the T  subsequent lines contains 2 space-separated integers describing the respective N and K values for a test case.

Output Format:
On a new line for each test case, 

Print the lexicographically smallest arrangement; 

If no absolute arrangement exists, print “CAPTAIN AMERICA EVADES”.

Constraints:
SubTask#1
1<=T<=10

1<=N<=10^5

0<=K<=N

SubTask#2
Original Constraints..

SubTask#3
Original Constraints..

Sample Input:
3

2 1

3 0

3 2

Sample Output:

2 1

1 2 3

CAPTAIN AMERICA EVADES

Explanation:
Case 1:

N=2 and K=1

Therefore the arrangement is [2,1].

Case 2:

N=3 and K=0

Therefore arrangement is [1,2,3].

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp studies at the university in the group which consists of *n* students (including himself). All they are registrated in the social net "TheContacnt!".

Not all students are equally sociable. About each student you know the value *a**i* — the maximum number of messages which the *i*-th student is agree to send per day. The student can't send messages to himself. 

In early morning Polycarp knew important news that the programming credit will be tomorrow. For this reason it is necessary to urgently inform all groupmates about this news using private messages. 

Your task is to make a plan of using private messages, so that:
 -  the student *i* sends no more than *a**i* messages (for all *i* from 1 to *n*); -  all students knew the news about the credit (initially only Polycarp knew it); -  the student can inform the other student only if he knows it himself. 
Let's consider that all students are numerated by distinct numbers from 1 to *n*, and Polycarp always has the number 1.

In that task you shouldn't minimize the number of messages, the moment of time, when all knew about credit or some other parameters. Find any way how to use private messages which satisfies requirements above.

Input Specification:
The first line contains the positive integer *n* (2<=≤<=*n*<=≤<=100) — the number of students. 

The second line contains the sequence *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=≤<=100), where *a**i* equals to the maximum number of messages which can the *i*-th student agree to send. Consider that Polycarp always has the number 1.

Output Specification:
Print -1 to the first line if it is impossible to inform all students about credit. 

Otherwise, in the first line print the integer *k* — the number of messages which will be sent. In each of the next *k* lines print two distinct integers *f* and *t*, meaning that the student number *f* sent the message with news to the student number *t*. All messages should be printed in chronological order. It means that the student, who is sending the message, must already know this news. It is assumed that students can receive repeated messages with news of the credit. 

If there are several answers, it is acceptable to print any of them.

Demo Input:
['4\n1 2 1 0\n', '6\n2 0 1 3 2 0\n', '3\n0 2 2\n']

Demo Output:
['3\n1 2\n2 4\n2 3\n', '6\n1 3\n3 4\n1 2\n4 5\n5 6\n4 6\n', '-1\n']

Note:
In the first test Polycarp (the student number 1) can send the message to the student number 2, who after that can send the message to students number 3 and 4. Thus, all students knew about the credit.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Students of IIITM love candies. There are N students in IIITM. They are standing in a line from Left to Right at Positions(1 to N). Dr. Niru decided to pick consecutive students from the line and give them candies. Now each student wish to have some number of candies A[i]. And they will take candies from Dr. Niru only if he has number of candies that is a multiple of A[i]. Now Dr. Niru wants that each student from his picked students should get the candies. So he wants to know the minimum number of candies he should have when he picks the students. Also at any particular time the students can wish for more or less number of candies. So Dr. Niru has to take that into account.

Please help Dr. Niru to select the minimum number of candies.

Input

The input file consists of several cases T (1 ≤ T ≤ 5). 
The first line of each case contains a positive integer N (1 ≤ N ≤ 16384) specifying the number of students in IIITM.  In next line there are N space separated values A[i..n] (1 ≤ A[i] ≤ 1000) which is the number of candies that student I wants. I is 1-Indexed.
In Next line there is Q i.e number of queries [1 ≤ Q ≤ 1000]. Queries are of two types –
1. 0 a b -> It means update the the number of candies that student a wants to b.
2. 1 a b -> Tell the minimum number of candies that Dr. Niru should have to satisfy the students from [a,b].

Output

For every query of the form 1 a b, you have to print the answer  modulo 1000000007 in a separate line.

SAMPLE INPUT
1
2
2 4
3
1 1 2
0 1 3
1 1 2

SAMPLE OUTPUT
4
12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are two infinite sources of water:  hot water of temperature $h$;  cold water of temperature $c$ ($c < h$). 

You perform the following procedure of alternating moves:  take one cup of the hot water and pour it into an infinitely deep barrel;  take one cup of the cold water and pour it into an infinitely deep barrel;  take one cup of the hot water $\dots$  and so on $\dots$ 

Note that you always start with the cup of hot water.

The barrel is initially empty. You have to pour at least one cup into the barrel. The water temperature in the barrel is an average of the temperatures of the poured cups.

You want to achieve a temperature as close as possible to $t$. So if the temperature in the barrel is $t_b$, then the absolute difference of $t_b$ and $t$ ($|t_b - t|$) should be as small as possible.

How many cups should you pour into the barrel, so that the temperature in it is as close as possible to $t$? If there are multiple answers with the minimum absolute difference, then print the smallest of them.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 3 \cdot 10^4$) — the number of testcases.

Each of the next $T$ lines contains three integers $h$, $c$ and $t$ ($1 \le c < h \le 10^6$; $c \le t \le h$) — the temperature of the hot water, the temperature of the cold water and the desired temperature in the barrel.


-----Output-----

For each testcase print a single positive integer — the minimum number of cups required to be poured into the barrel to achieve the closest temperature to $t$.


-----Example-----
Input
3
30 10 20
41 15 30
18 13 18

Output
2
7
1



-----Note-----

In the first testcase the temperature after $2$ poured cups: $1$ hot and $1$ cold is exactly $20$. So that is the closest we can achieve.

In the second testcase the temperature after $7$ poured cups: $4$ hot and $3$ cold is about $29.857$. Pouring more water won't get us closer to $t$ than that.

In the third testcase the temperature after $1$ poured cup: $1$ hot is $18$. That's exactly equal to $t$.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
It is well known that Berland has *n* cities, which form the Silver ring — cities *i* and *i*<=+<=1 (1<=≤<=*i*<=&lt;<=*n*) are connected by a road, as well as the cities *n* and 1. The goverment have decided to build *m* new roads. The list of the roads to build was prepared. Each road will connect two cities. Each road should be a curve which lies inside or outside the ring. New roads will have no common points with the ring (except the endpoints of the road).

Now the designers of the constructing plan wonder if it is possible to build the roads in such a way that no two roads intersect (note that the roads may intersect at their endpoints). If it is possible to do, which roads should be inside the ring, and which should be outside?

Input Specification:
The first line contains two integers *n* and *m* (4<=≤<=*n*<=≤<=100,<=1<=≤<=*m*<=≤<=100). Each of the following *m* lines contains two integers *a**i* and *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*,<=*a**i*<=≠<=*b**i*). No two cities will be connected by more than one road in the list. The list will not contain the roads which exist in the Silver ring.

Output Specification:
If it is impossible to build the roads in such a way that no two roads intersect, output Impossible. Otherwise print *m* characters. *i*-th character should be i, if the road should be inside the ring, and o if the road should be outside the ring. If there are several solutions, output any of them.

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

Demo Output:
['io\n', 'ooo\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Situation
You have been hired by a company making electric garage doors. Accidents with the present product line have resulted in numerous damaged cars, broken limbs and several killed pets. Your mission is to write a safer version of their controller software.

# Specification
We always start with a closed door. The remote control has exactly one button, with the following behaviour.

+ If the door is closed, a push starts opening the door, and vice-versa
+ It takes 5 seconds for the door to open or close completely
+ While the door is moving, one push pauses movement, another push resumes movement in the same direction

In order to make the door safer, it has been equiped with resistance-based obstacle detection. When the door detects an obstacle, it must immediately reverse the direction of movement.

# Input
A string where each character represents one second, with the following possible values.

* ```'.'``` No event
* ```'P'``` Button has been pressed
* ```'O'``` Obstacle has been detected (supersedes P)

As an example, ```'..P....'``` means that nothing happens for two seconds, then the button is pressed, then no further events.

# Output
A string where each character represents one second and indicates the position of the door (0 if fully closed and 5 fully open). The door starts moving immediately, hence its position changes at the same second as the event.

# Example
```..P...O.....``` as input should yield
```001234321000``` as output

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Flatland has recently introduced a new type of an eye check for the driver's licence. The check goes like that: there is a plane with mannequins standing on it. You should tell the value of the minimum angle with the vertex at the origin of coordinates and with all mannequins standing inside or on the boarder of this angle. 

As you spend lots of time "glued to the screen", your vision is impaired. So you have to write a program that will pass the check for you.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=105) — the number of mannequins.

Next *n* lines contain two space-separated integers each: *x**i*,<=*y**i* (|*x**i*|,<=|*y**i*|<=≤<=1000) — the coordinates of the *i*-th mannequin. It is guaranteed that the origin of the coordinates has no mannequin. It is guaranteed that no two mannequins are located in the same point on the plane.

Output Specification:
Print a single real number — the value of the sought angle in degrees. The answer will be considered valid if the relative or absolute error doesn't exceed 10<=-<=6.

Demo Input:
['2\n2 0\n0 2\n', '3\n2 0\n0 2\n-2 2\n', '4\n2 0\n0 2\n-2 0\n0 -2\n', '2\n2 1\n1 2\n']

Demo Output:
['90.0000000000\n', '135.0000000000\n', '270.0000000000\n', '36.8698976458\n']

Note:
Solution for the first sample test is shown below: 

Solution for the second sample test is shown below: 

Solution for the third sample test is shown below: 

Solution for the fourth sample test is shown below:

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