vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Hierarchy

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
Nick's company employed *n* people. Now Nick needs to build a tree hierarchy of «supervisor-surbodinate» relations in the company (this is to say that each employee, except one, has exactly one supervisor). There are *m* applications written in the following form: «employee *a**i* is ready to become a supervisor of employee *b**i* at extra cost *c**i*». The qualification *q**j* of each employee is known, and for each application the following is true: *q**a**i*<=&gt;<=*q**b**i*. 

Would you help Nick calculate the minimum cost of such a hierarchy, or find out that it is impossible to build it.

Input Specification:
The first input line contains integer *n* (1<=≤<=*n*<=≤<=1000) — amount of employees in the company. The following line contains *n* space-separated numbers *q**j* (0<=≤<=*q**j*<=≤<=106)— the employees' qualifications. The following line contains number *m* (0<=≤<=*m*<=≤<=10000) — amount of received applications. The following *m* lines contain the applications themselves, each of them in the form of three space-separated numbers: *a**i*, *b**i* and *c**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*, 0<=≤<=*c**i*<=≤<=106). Different applications can be similar, i.e. they can come from one and the same employee who offered to become a supervisor of the same person but at a different cost. For each application *q**a**i*<=&gt;<=*q**b**i*.

Output Specification:
Output the only line — the minimum cost of building such a hierarchy, or -1 if it is impossible to build it.

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

Demo Output:
['11\n', '-1\n']

Note:
In the first sample one of the possible ways for building a hierarchy is to take applications with indexes 1, 2 and 4, which give 11 as the minimum total cost. In the second sample it is impossible to build the required hierarchy, so the answer is -1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Toad Rash has a binary string s. A binary string consists only of zeros and ones.

Let n be the length of s.

Rash needs to find the number of such pairs of integers l, r that 1 ≤ l ≤ r ≤ n and there is at least one pair of integers x, k such that 1 ≤ x, k ≤ n, l ≤ x < x + 2k ≤ r, and s_x = s_{x+k} = s_{x+2k}.

Find this number of pairs for Rash.

Input

The first line contains the string s (1 ≤ |s| ≤ 300 000), consisting of zeros and ones.

Output

Output one integer: the number of such pairs of integers l, r that 1 ≤ l ≤ r ≤ n and there is at least one pair of integers x, k such that 1 ≤ x, k ≤ n, l ≤ x < x + 2k ≤ r, and s_x = s_{x+k} = s_{x+2k}.

Examples

Input


010101


Output


3


Input


11001100


Output


0

Note

In the first example, there are three l, r pairs we need to count: 1, 6; 2, 6; and 1, 5.

In the second example, there are no values x, k for the initial string, so the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N integers X_1, X_2, \cdots, X_N, and we know that A_i \leq X_i \leq B_i.
Find the number of different values that the median of X_1, X_2, \cdots, X_N can take.

-----Notes-----
The median of X_1, X_2, \cdots, X_N is defined as follows. Let x_1, x_2, \cdots, x_N be the result of sorting X_1, X_2, \cdots, X_N in ascending order.
 - If N is odd, the median is x_{(N+1)/2};
 - if N is even, the median is (x_{N/2} + x_{N/2+1}) / 2.

-----Constraints-----
 - 2 \leq N \leq 2 \times 10^5
 - 1 \leq A_i \leq B_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 B_1
A_2 B_2
:
A_N B_N

-----Output-----
Print the answer.

-----Sample Input-----
2
1 2
2 3

-----Sample Output-----
3

 - If X_1 = 1 and X_2 = 2, the median is \frac{3}{2};
 - if X_1 = 1 and X_2 = 3, the median is 2;
 - if X_1 = 2 and X_2 = 2, the median is 2;
 - if X_1 = 2 and X_2 = 3, the median is \frac{5}{2}.
Thus, the median can take three values: \frac{3}{2}, 2, and \frac{5}{2}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Do you know a story about the three musketeers? Anyway, you will learn about its origins now.

Richelimakieu is a cardinal in the city of Bearis. He is tired of dealing with crime by himself. He needs three brave warriors to help him to fight against bad guys.

There are n warriors. Richelimakieu wants to choose three of them to become musketeers but it's not that easy. The most important condition is that musketeers must know each other to cooperate efficiently. And they shouldn't be too well known because they could be betrayed by old friends. For each musketeer his recognition is the number of warriors he knows, excluding other two musketeers.

Help Richelimakieu! Find if it is possible to choose three musketeers knowing each other, and what is minimum possible sum of their recognitions.


-----Input-----

The first line contains two space-separated integers, n and m (3 ≤ n ≤ 4000, 0 ≤ m ≤ 4000) — respectively number of warriors and number of pairs of warriors knowing each other.

i-th of the following m lines contains two space-separated integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}). Warriors a_{i} and b_{i} know each other. Each pair of warriors will be listed at most once.


-----Output-----

If Richelimakieu can choose three musketeers, print the minimum possible sum of their recognitions. Otherwise, print "-1" (without the quotes).


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

Output
2

Input
7 4
2 1
3 6
5 1
1 7

Output
-1



-----Note-----

In the first sample Richelimakieu should choose a triple 1, 2, 3. The first musketeer doesn't know anyone except other two musketeers so his recognition is 0. The second musketeer has recognition 1 because he knows warrior number 4. The third musketeer also has recognition 1 because he knows warrior 4. Sum of recognitions is 0 + 1 + 1 = 2.

The other possible triple is 2, 3, 4 but it has greater sum of recognitions, equal to 1 + 1 + 1 = 3.

In the second sample there is no triple of warriors knowing each other.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is an integer sequence of length 2^N: A_0, A_1, ..., A_{2^N-1}. (Note that the sequence is 0-indexed.)
For every integer K satisfying 1 \leq K \leq 2^N-1, solve the following problem:
 - Let i and j be integers. Find the maximum value of A_i + A_j where 0 \leq i < j \leq 2^N-1 and (i or j) \leq K.
Here, or denotes the bitwise OR.

-----Constraints-----
 - 1 \leq N \leq 18
 - 1 \leq A_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_0 A_1 ... A_{2^N-1}

-----Output-----
Print 2^N-1 lines.
In the i-th line, print the answer of the problem above for K=i.

-----Sample Input-----
2
1 2 3 1

-----Sample Output-----
3
4
5

For K=1, the only possible pair of i and j is (i,j)=(0,1), so the answer is A_0+A_1=1+2=3.
For K=2, the possible pairs of i and j are (i,j)=(0,1),(0,2).
When (i,j)=(0,2), A_i+A_j=1+3=4. This is the maximum value, so the answer is 4.
For K=3, the possible pairs of i and j are (i,j)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3) .
When (i,j)=(1,2), A_i+A_j=2+3=5. This is the maximum value, so the answer is 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the number of ways to choose a pair of an even number and an odd number from the positive integers between 1 and K (inclusive). The order does not matter.

-----Constraints-----
 - 2\leq K\leq 100
 - K is an integer.

-----Input-----
Input is given from Standard Input in the following format:
K

-----Output-----
Print the number of ways to choose a pair of an even number and an odd number from the positive integers between 1 and K (inclusive).

-----Sample Input-----
3

-----Sample Output-----
2

Two pairs can be chosen: (2,1) and (2,3).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The robot is located on a checkered rectangular board of size $n \times m$ ($n$ rows, $m$ columns). The rows in the board are numbered from $1$ to $n$ from top to bottom, and the columns — from $1$ to $m$ from left to right.

The robot is able to move from the current cell to one of the four cells adjacent by side.

The sequence of commands $s$ executed by the robot is given. Each command is denoted by one of the symbols 'L', 'R', 'D' or 'U', and triggers the movement to left, right, down or up, respectively.

The robot can start its movement in any cell. The robot executes the commands starting from the first one, strictly in the order in which they are listed in $s$. If the robot moves beyond the edge of the board, it falls and breaks. A command that causes the robot to break is not considered successfully executed.

The robot's task is to execute as many commands as possible without falling off the board. For example, on board $3 \times 3$, if the robot starts a sequence of actions $s=$"RRDLUU" ("right", "right", "down", "left", "up", "up") from the central cell, the robot will perform one command, then the next command will force him to cross the edge. If the robot starts moving from the cell $(2, 1)$ (second row, first column) then all commands will be executed successfully and the robot will stop at the cell $(1, 2)$ (first row, second column).

The robot starts from cell $(2, 1)$ (second row, first column). It moves right, right, down, left, up, and up. In this case it ends in the cell $(1, 2)$ (first row, second column).

Determine the cell from which the robot should start its movement in order to execute as many commands as possible.


-----Input-----

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

The next $2t$ lines contain descriptions of the test cases.

In the description of each test case, the first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^6$) — the height and width of the field that the robot is located on. The second line of the description is a string $s$ consisting solely of characters 'L', 'R', 'D' and 'U' — the sequence of commands the robot executes. The string has a length from $1$ to $10^6$ commands.

It is guaranteed that the total length of $s$ over all test cases does not exceed $10^6$.


-----Output-----

Print $t$ lines, each of which contains the answer to the corresponding test case. The answer to the test case are two integers $r$ ($1 \leq r \leq n$) and $c$ ($1 \leq c \leq m$), separated by a space — the coordinates of the cell (row number and column number) from which the robot should start moving to perform as many commands as possible.

If there are several such cells, you may output any of them.


-----Examples-----

Input
4
1 1
L
1 2
L
3 3
RRDLUU
4 3
LUURRDDLLLUU
Output
1 1
1 2
2 1
3 2


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Robot Turtles is one of Theta’s favorite games. In this game, kindergarteners learn how to “code” by creating programs that move a turtle from a starting field to a diamond. Robot Turtles is reportedly the most successful game funded by the Kickstarter incubator.

In the actual board game, an adult plays the role of the “turtle master,” which is the person that plays the role of a CPU to execute the program. As you can imagine, this is a pretty boring task that cries out for automation: in this problem, you are asked to write a program that automates the task of the turtle master.

Robot Turtles is played on an $8 \times 8$ board. There is one turtle (marked with the letter T), which always starts out at the bottom-left field, facing right. The board contains empty squares (marked as .), castles made out of rock (C), and castles made out of ice (I). The diamond is marked with a D. The turtle may move only onto empty squares and the square on which the diamond is located.

A turtle program contains $4$ kinds of instructions, marked by a single letter.
 - F The turtle moves one field forward in the direction it is facing. If the turtle faces a castle or the border of the board, a program error occurs.
 - R The turtle turns $90$ degrees to the right (the turtle will just turn and stay on the same field).
 - L The turtle turns $90$ degrees to the left (the turtle will just turn and stay on the same field).
 - X The turtle fires a laser in the direction it is facing. If the square it is facing contains an ice castle, the ice castle will melt and the square will turn into an empty square. Otherwise, a program error occurs. The turtle will not move or change direction. It is a program error to fire the laser at empty squares, rock castles or outside the board.

-----Input-----
The input consists of $9$ lines. The first $8$ lines contains the board, each line representing the squares in a row of the board. The turtle will always be at the bottom-left. There will be exactly $1$ diamond. The $9^{\text {th}}$ line contains the program the turtle master is asked to execute, which contains at least $1$ and at most $60$ instructions.

-----Output-----
Output Diamond! if the entire program can be executed without program error and if the turtle is on the diamond square after the program has been executed. Output Bug! if a program error occurred, or if the turtle does not end up on the diamond square!

-----Examples-----
Sample Input 1:
........
........
........
...CC...
..C.DC..
.C..C...
C.IC....
T.C.....
FLFRXFLFRFLFRF
Sample Output 1:
Diamond!

Sample Input 2:
........
........
........
...CC...
..C.DC..
.C..C...
C.IC....
T.C.....
FLFRFLFRFLFRF
Sample Output 2:
Bug!

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp is a music editor at the radio station. He received a playlist for tomorrow, that can be represented as a sequence *a*1,<=*a*2,<=...,<=*a**n*, where *a**i* is a band, which performs the *i*-th song. Polycarp likes bands with the numbers from 1 to *m*, but he doesn't really like others. 

We define as *b**j* the number of songs the group *j* is going to perform tomorrow. Polycarp wants to change the playlist in such a way that the minimum among the numbers *b*1,<=*b*2,<=...,<=*b**m* will be as large as possible.

Find this maximum possible value of the minimum among the *b**j* (1<=≤<=*j*<=≤<=*m*), and the minimum number of changes in the playlist Polycarp needs to make to achieve it. One change in the playlist is a replacement of the performer of the *i*-th song with any other group.

Input Specification:
The first line of the input contains two integers *n* and *m* (1<=≤<=*m*<=≤<=*n*<=≤<=2000).

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109), where *a**i* is the performer of the *i*-th song.

Output Specification:
In the first line print two integers: the maximum possible value of the minimum among the *b**j* (1<=≤<=*j*<=≤<=*m*), where *b**j* is the number of songs in the changed playlist performed by the *j*-th band, and the minimum number of changes in the playlist Polycarp needs to make.

In the second line print the changed playlist.

If there are multiple answers, print any of them.

Demo Input:
['4 2\n1 2 3 2\n', '7 3\n1 3 2 2 2 2 1\n', '4 4\n1000000000 100 7 1000000000\n']

Demo Output:
['2 1\n1 2 1 2 \n', '2 1\n1 3 3 2 2 2 1 \n', '1 4\n1 2 3 4 \n']

Note:
In the first sample, after Polycarp's changes the first band performs two songs (*b*<sub class="lower-index">1</sub> = 2), and the second band also performs two songs (*b*<sub class="lower-index">2</sub> = 2). Thus, the minimum of these values equals to 2. It is impossible to achieve a higher minimum value by any changes in the playlist. 

In the second sample, after Polycarp's changes the first band performs two songs (*b*<sub class="lower-index">1</sub> = 2), the second band performs three songs (*b*<sub class="lower-index">2</sub> = 3), and the third band also performs two songs (*b*<sub class="lower-index">3</sub> = 2). Thus, the best minimum value is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Create a function that finds the [integral](https://en.wikipedia.org/wiki/Integral) of the expression passed.

In order to find the integral all you need to do is add one to the `exponent` (the second argument), and divide the `coefficient` (the first argument) by that new number.

For example for `3x^2`, the integral would be `1x^3`: we added 1 to the exponent, and divided the coefficient by that new number).

Notes:
* The output should be a string.
* The coefficient and exponent is always a positive integer.


## Examples

```
 3, 2  -->  "1x^3"
12, 5  -->  "2x^6"
20, 1  -->  "10x^2"
40, 3  -->  "10x^4"
90, 2  -->  "30x^3"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Slavko decided to challenge Mirko! He gave him a real number $P$ and a bag full of pieces of paper with exactly one number between $1$ and $5$ inclusive written on each paper. There is an unlimited quantity of each type of paper.

Mirko’s task is to pick the minimum number of papers in a way that the average of the numbers written on them equals exactly $P$.

-----Input-----
First and only line of input contains real number $P$. $P$ will have between 1 and 9 decimal places, inclusive $(1 \leq P \leq 5)$.

-----Output-----
First and only line of output should contain five nonnegative integers – numbers of ones, twos, threes, fours and fives used, respectively. If there are multiple solutions, output any one of them.

-----Examples-----
Sample Input 1:
5.0
Sample Output 1:
0 0 0 0 1

Sample Input 2:
4.5
Sample Output 2:
0 0 0 1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ravi is very good student in mathematics and he also like Even numbers very much .

On the other hand his friend Jhon like Odd numbers . Both of them are preparing for IIT JEE Advance .One day they are solving a  question together the question was Find the sum of first $n$ terms of the given series  $1^2+2.2^2+3^2+2.4^2+5^2+2.6^2+...........$
If the sum is odd then Jhon will be happy and will solve 2 more questions,and Ravi will not attempt more questions. If sum is even Ravi will  be happy and will solve 2 more questions and Jhon will not attempt more questions. 
So Your task is to decide who will solve more questions.

-----Input:-----
- First line will contain $n$, number of terms  in the given series.

-----Output:-----
Output single line "Ravi" if he solve more questions or "Jhon" if he solve more questions.

-----Constraints-----
- $1 \leq n \leq 100$

-----Sample Input:-----
2

3   

-----Sample Output:-----
Jhon       
Ravi       

-----EXPLANATION:-----
In the first test cases  sum of 2 terms is 9 (according to the given series) which is an odd number   so Jhon will solve 2 more questions and Ravi will not attempt more questions.
In second test case sum of 3 terms is 18 (according to the given series) which is an  even number according to the given series  so Ravi will solve 3 more questions and Jhon will not attempt more questions.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shil, Aditya and Utkarsh go to a candy shop. There are N candies present in the shop, which are indexed from 1 to N. All three of them select one candy to eat.

However, a candy tastes delicious if and only if, the index of candy chosen by Shil is strictly less than the index of candy chosen by Aditya and the index of candy chosen by Aditya is strictly greater than index of candy chosen by Utkarsh. 

To state in simple Mathematical terms, if Shil chooses i^th candy, Aditya chooses j^th candy and Utkarsh chooses k^th candy, then the candies would taste delicious 
if and only if i < j and j > k.
You have to find the total number of ways in which they can choose candies such that the candies would taste delicious to them. Note that all of them choose distinct number of candies i.e.,  i!=j and j!=k and i!=k.

Input format:
The only line of input consists of a single integer N denoting the total number of candies.   

Output format:
Find the total number of ways by which all three can choose candies such that the candies would taste delicious to them.  

Constraints:
3 ≤ N ≤ 1000

SAMPLE INPUT
4

SAMPLE OUTPUT
8

Explanation

All the possible ways to choose candies are:  
[1,3,2]  
[2,3,1]  
[2,4,3]  
[3,4,2]  
[1,4,3]  
[3,4,1]  
[2,4,1]  
[1,4,2]  

The first integer in all the tuples denotes index of candy chosen by Shil, the second integer denotes index of candy chosen by Aditya and the third integer denotes index of candy chosen by Utkarsh.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
AtCoDeer the deer wants a directed graph that satisfies the following conditions:

* The number of vertices, N, is at most 300.
* There must not be self-loops or multiple edges.
* The vertices are numbered from 1 through N.
* Each edge has either an integer weight between 0 and 100 (inclusive), or a label `X` or `Y`.
* For every pair of two integers (x,y) such that 1 ≤ x ≤ A, 1 ≤ y ≤ B, the shortest distance from Vertex S to Vertex T in the graph where the edges labeled `X` have the weight x and the edges labeled `Y` have the weight y, is d_{x,y}.



Construct such a graph (and a pair of S and T) for him, or report that it does not exist. Refer to Output section for output format.

Constraints

* 1 ≤ A,B ≤ 10
* 1 ≤ d_{x,y} ≤ 100 (1 ≤ x ≤ A, 1 ≤ y ≤ B)
* All input values are integers.

Input

Input is given from Standard Input in the following format:


A B
d_{1,1} d_{1,2} .. d_{1,B}
d_{2,1} d_{2,2} .. d_{2,B}
:
d_{A,1} d_{A,2} .. d_{A,B}


Output

If no graph satisfies the condition, print `Impossible`.

If there exists a graph that satisfies the condition, print `Possible` in the first line. Then, in the subsequent lines, print the constructed graph in the following format:


N M
u_1 v_1 c_1
u_2 v_2 c_2
:
u_M v_M c_M
S T


Here, M is the number of the edges, and u_i, v_i, c_i represent edges as follows: there is an edge from Vertex u_i to Vertex v_i whose weight or label is c_i.

Also refer to Sample Outputs.

Examples

Input

2 3
1 2 2
1 2 3


Output

Possible
3 4
1 2 X
2 3 1
3 2 Y
1 3 Y
1 3


Input

1 3
100 50 1


Output

Impossible

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