vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: R3D3’s Summer Adventure

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
R3D3 spent some time on an internship in MDCS. After earning enough money, he decided to go on a holiday somewhere far, far away. He enjoyed suntanning, drinking alcohol-free cocktails and going to concerts of popular local bands. While listening to "The White Buttons" and their hit song "Dacan the Baker", he met another robot for whom he was sure is the love of his life. Well, his summer, at least. Anyway, R3D3 was too shy to approach his potential soulmate, so he decided to write her a love letter. However, he stumbled upon a problem. Due to a terrorist threat, the Intergalactic Space Police was monitoring all letters sent in the area. Thus, R3D3 decided to invent his own alphabet, for which he was sure his love would be able to decipher.

There are *n* letters in R3D3’s alphabet, and he wants to represent each letter as a sequence of '0' and '1', so that no letter’s sequence is a prefix of another letter's sequence. Since the Intergalactic Space Communications Service has lately introduced a tax for invented alphabets, R3D3 must pay a certain amount of money for each bit in his alphabet’s code (check the sample test for clarifications). He is too lovestruck to think clearly, so he asked you for help.

Given the costs *c*0 and *c*1 for each '0' and '1' in R3D3’s alphabet, respectively, you should come up with a coding for the alphabet (with properties as above) with minimum total cost.

Input Specification:
The first line of input contains three integers *n* (2<=≤<=*n*<=≤<=108), *c*0 and *c*1 (0<=≤<=*c*0,<=*c*1<=≤<=108) — the number of letters in the alphabet, and costs of '0' and '1', respectively.

Output Specification:
Output a single integer — minimum possible total a cost of the whole alphabet.

Demo Input:
['4 1 2\n']

Demo Output:
['12\n']

Note:
There are 4 letters in the alphabet. The optimal encoding is "00", "01", "10", "11". There are 4 zeroes and 4 ones used, so the total cost is 4·1 + 4·2 = 12.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a String S , print the reverse of the string as output.
Example 1:
Input: S = "GeeksforGeeks"
Output: "skeeGrofskeeG" 
Explanation: Element at first is at last and
last is at first, second is at second last and 
second last is at second position and so on .
Example 2:
Input: S = "ReversE"
Output: "EsreveR"
Explanation: "E" at first and "R" at last and
"e" at second last and "s" at second and
so on .
Your Task:  
You dont need to read input or print anything. Complete the function revStr() which takes S as input parameter and returns the reversed string .
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
Constraints:
1<= |S| <=1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A Maze is given as n*n matrix of blocks where source block is the upper left most block i.e., matrix[0][0] and destination block is lower rightmost block i.e., matrix[n-1][n-1]. A rat starts from source and has to reach the destination. The rat can move in only two directions: first forward if possible or down. If multiple solutions exist, the shortest earliest hop will be accepted. For the same hop distance at any point, forward will be preferred over downward. In the maze matrix, 0 means the block is the dead end and non-zero number means the block can be used in the path from source to destination. The non-zero value of mat[i][j] indicates number of maximum jumps rat can make from cell mat[i][j]. In this variation, Rat is allowed to jump multiple steps at a time instead of 1. Find a matrix which describes the position the rat to reach at the destination.
 
Example:
Input: {{2,1,0,0},{3,0,0,1},{0,1,0,1},
{0,0,0,1}}
Output: {{1,0,0,0},{1,0,0,1},{0,0,0,1},
{0,0,0,1}}
Explanation: Rat started with matrix[0][0] and 
can jump up to 2 steps right/down. First check 
matrix[0][1] as it is 1, next check 
matrix[0][2] ,this won't lead to the solution. 
Then check matrix[1][0], as this is 3(non-zero)
,so we can make 3 jumps to reach matrix[1][3]. 
From matrix[1][3] we can move downwards taking 
1 jump each time to reach destination at 
matrix[3][3].
Example 2:
Input: {{2,1,0,0},{2,0,0,1},{0,1,0,1},
{0,0,0,1}}
Output: {{-1}}
Explanation: As no path exists so, -1.
 
Your Task:
You don't need to read or print anyhting, Your task is to complete the function ShortestDistance() which takes the matrix as input parameter and returns a matrix of size n if path exists otherwise returns a matrix of 1x1 which contains -1. In output matrix, 1 at (i, j) represents the cell is taken into the path otherwise 0 if any path exists.
 
Expected Time Complexity: O(n*n*k) where k is max(matrix[i][j])
Expected Space Complexity: O(1)
 
Constraints:
1 <= n <= 50
1 <= matrix[i][j] <= 20

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One of Arkady's friends works at a huge radio telescope. A few decades ago the telescope has sent a signal $s$ towards a faraway galaxy. Recently they've received a response $t$ which they believe to be a response from aliens! The scientists now want to check if the signal $t$ is similar to $s$.

The original signal $s$ was a sequence of zeros and ones (everyone knows that binary code is the universe-wide language). The returned signal $t$, however, does not look as easy as $s$, but the scientists don't give up! They represented $t$ as a sequence of English letters and say that $t$ is similar to $s$ if you can replace all zeros in $s$ with some string $r_0$ and all ones in $s$ with some other string $r_1$ and obtain $t$. The strings $r_0$ and $r_1$ must be different and non-empty.

Please help Arkady's friend and find the number of possible replacements for zeros and ones (the number of pairs of strings $r_0$ and $r_1$) that transform $s$ to $t$.


-----Input-----

The first line contains a string $s$ ($2 \le |s| \le 10^5$) consisting of zeros and ones — the original signal.

The second line contains a string $t$ ($1 \le |t| \le 10^6$) consisting of lowercase English letters only — the received signal.

It is guaranteed, that the string $s$ contains at least one '0' and at least one '1'.


-----Output-----

Print a single integer — the number of pairs of strings $r_0$ and $r_1$ that transform $s$ to $t$.

In case there are no such pairs, print $0$.


-----Examples-----
Input
01
aaaaaa

Output
4

Input
001
kokokokotlin

Output
2



-----Note-----

In the first example, the possible pairs $(r_0, r_1)$ are as follows:  "a", "aaaaa"  "aa", "aaaa"  "aaaa", "aa"  "aaaaa", "a"  

The pair "aaa", "aaa" is not allowed, since $r_0$ and $r_1$ must be different.

In the second example, the following pairs are possible:   "ko", "kokotlin"  "koko", "tlin"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A substring of a string is a contiguous subsequence of that string. So, string bca is substring of string abcabc, but string cc is not.

A repeating block is a string formed by concatenating some string with itself. So, string abcabc is a repeating block, but strings abcabd, ababab are not.

You've got a sequence of Latin characters (string). At each step you find the shortest substring that is a repeating block, if there exists more than one you must choose the leftmost. As the substring is of form XX (X — some string) you replace this substring with X, in other words you delete one of the X substrings in the substring. You repeat this process until there remains no repeating block in the string. 

How would the final string looks like? Look at the sample explanation to understand the statement more precise.

Input

In the first line of input you're given a string of small Latin characters with length between 1 to 50000, inclusive.

Output

Print the final string after applying changes.

Examples

Input

abccabc


Output

abc


Input

aaaabaaab


Output

ab


Input

birdbirdbirdistheword


Output

birdistheword

Note

At the first sample the string transforms as follows: abccabc →  abcabc →  abc.

At the second sample the string transforms as follows: aaaabaaab →  aaabaaab →  aabaaab →  abaaab →  abaab →  abab →  ab.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On an $8 \times 8$ grid, some horizontal rows have been painted red, and some vertical columns have been painted blue, in some order. The stripes are drawn sequentially, one after the other. When the stripe is drawn, it repaints all the cells through which it passes.

Determine which color was used last.

The red stripe was painted after the blue one, so the answer is R.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \leq t \leq 4000$) — the number of test cases. The description of test cases follows. There is an empty line before each test case.

Each test case consists of $8$ lines, each containing $8$ characters. Each of these characters is either 'R', 'B', or '.', denoting a red square, a blue square, and an unpainted square, respectively.

It is guaranteed that the given field is obtained from a colorless one by drawing horizontal red rows and vertical blue columns.

At least one stripe is painted.


-----Output-----

For each test case, output 'R' if a red stripe was painted last, and 'B' if a blue stripe was painted last (without quotes).


-----Examples-----

Input
4
....B...
....B...
....B...
RRRRRRRR
....B...
....B...
....B...
....B...
RRRRRRRB
B......B
B......B
B......B
B......B
B......B
B......B
RRRRRRRB
RRRRRRBB
.B.B..BB
RRRRRRBB
.B.B..BB
.B.B..BB
RRRRRRBB
.B.B..BB
.B.B..BB
........
........
........
RRRRRRRR
........
........
........
........
Output
R
B
B
R


-----Note-----

The first test case is pictured in the statement.

In the second test case, the first blue column is painted first, then the first and last red rows, and finally the last blue column. Since a blue stripe is painted last, the answer is B.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a contest containing 2 problems A and B. 

2 strong participants P and Q participated in the contest and solved both the problems.

P made AC submissions on problems A and B at time instants P_{A} and P_{B} respectively while Q made AC submissions on problems A and B at time instants Q_{A} and Q_{B}.

It is given that the time penalty is the minimum time instant at which a participant has solved both the problems. Also the participant with the lower time penalty will have a better rank.

Determine which participant got the better rank or if there is a TIE.

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

- The first line will contain T, number of test cases. Then the test cases follow.
- Each test case contains a single line of input, four integers P_{A}, P_{B}, Q_{A}, Q_{B}.

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

For each test case, output P if P got a better rank, Q if Q got a better rank, TIE otherwise.

Note that output is case-insensitive i.e. P and p both are considered the same.

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

$1 ≤ T ≤ 1000$
$1 ≤ P_{A}, P_{B}, Q_{A}, Q_{B} ≤ 100$

----- Sample Input 1 ------ 
4
5 10 2 12
10 30 15 15
20 8 4 20
6 6 6 6

----- Sample Output 1 ------ 
P
Q
TIE
TIE

----- explanation 1 ------ 
Test Case $1$: 
- Time penalty incurred by participant $P = 10$. 
- Time penalty incurred by participant $Q = 12$.

Since $10 < 12$, $P$ gets a better rank.

Test Case $2$: 
- Time penalty incurred by participant $P = 30$. 
- Time penalty incurred by participant $Q = 15$. 

Since $15 < 30$, $Q$ gets a better rank.

Test Case $3$: 
- Time penalty incurred by participant $P = 20$. 
- Time penalty incurred by participant $Q = 20$. 

Since $20 = 20$, $P$ and $Q$ gets a same rank (TIE).

Test Case $4$: 
- Time penalty incurred by participant $P = 6$. 
- Time penalty incurred by participant $Q = 6$. 

Since $6 = 6$, $P$ and $Q$ gets a same rank (TIE).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Salve, mi amice.

Et tu quidem de lapis philosophorum. Barba non facit philosophum. Labor omnia vincit. Non potest creatio ex nihilo. Necesse est partibus.

Rp:

    I Aqua Fortis

    I Aqua Regia

    II Amalgama

    VII Minium

    IV Vitriol

Misce in vitro et æstus, et nil admirari. Festina lente, et nulla tenaci invia est via.

Fac et spera,

Vale,

Nicolas Flamel


-----Input-----

The first line of input contains several space-separated integers a_{i} (0 ≤ a_{i} ≤ 100).


-----Output-----

Print a single integer.


-----Examples-----
Input
2 4 6 8 10

Output
1

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

You plan to draw a black-and-white painting on a rectangular canvas. The painting will be a grid array of pixels, either black or white. You can paint black or white lines or dots on the initially white canvas.

You can apply a sequence of the following two operations in any order.

* Painting pixels on a horizontal or vertical line segment, single pixel wide and two or more pixel long, either black or white. This operation has a cost proportional to the length (the number of pixels) of the line segment multiplied by a specified coefficient in addition to a specified constant cost.
* Painting a single pixel, either black or white. This operation has a specified constant cost.



You can overpaint already painted pixels as long as the following conditions are satisfied.

* The pixel has been painted at most once before. Overpainting a pixel too many times results in too thick layers of inks, making the picture look ugly. Note that painting a pixel with the same color is also counted as overpainting. For instance, if you have painted a pixel with black twice, you can paint it neither black nor white anymore.
* The pixel once painted white should not be overpainted with the black ink. As the white ink takes very long to dry, overpainting the same pixel black would make the pixel gray, rather than black. The reverse, that is, painting white over a pixel already painted black, has no problem.



Your task is to compute the minimum total cost to draw the specified image.

Input

The input consists of a single test case. The first line contains five integers $n$, $m$, $a$, $b$, and $c$, where $n$ ($1 \leq n \leq 40$) and $m$ ($1 \leq m \leq 40$) are the height and the width of the canvas in the number of pixels, and $a$ ($0 \leq a \leq 40$), $b$ ($0 \leq b \leq 40$), and $c$ ($0 \leq c \leq 40$) are constants defining painting costs as follows. Painting a line segment of length $l$ costs $al + b$ and painting a single pixel costs $c$. These three constants satisfy $c \leq a + b$.

The next $n$ lines show the black-and-white image you want to draw. Each of the lines contains a string of length $m$. The $j$-th character of the $i$-th string is ‘#’ if the color of the pixel in the $i$-th row and the $j$-th column is to be black, and it is ‘.’ if the color is to be white.

Output

Output the minimum cost.

Sample Input 1


3 3 1 2 3
.#.

.#.


Sample Output 1


10


Sample Input 2


2 7 0 1 1
.###
.###


Sample Output 2


3


Sample Input 3


5 5 1 4 4
..#..
..#..
.##
..#..
..#..


Sample Output 3


24


Sample Input 4


7 24 1 10 10
...###..#####....###.
.#...#...#.#....#..#...#
.#..#......#....#.#.....
.#..#......#####..#.....
.#..#......#......#.....
.#...#...#.#.......#...#
...###..#........###.


Sample Output 4


256






Example

Input

3 3 1 2 3
.#.
###
.#.


Output

10

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are $n$ students in a school class, the rating of the $i$-th student on Codehorses is $a_i$. You have to form a team consisting of $k$ students ($1 \le k \le n$) such that the ratings of all team members are distinct.

If it is impossible to form a suitable team, print "NO" (without quotes). Otherwise print "YES", and then print $k$ distinct numbers which should be the indices of students in the team you form. If there are multiple answers, print any of them.

Input Specification:
The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 100$) — the number of students and the size of the team you have to form.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$), where $a_i$ is the rating of $i$-th student.

Output Specification:
If it is impossible to form a suitable team, print "NO" (without quotes). Otherwise print "YES", and then print $k$ distinct integers from $1$ to $n$ which should be the indices of students in the team you form. All the ratings of the students in the team should be distinct. You may print the indices in any order. If there are multiple answers, print any of them.

Assume that the students are numbered from $1$ to $n$.

Demo Input:
['5 3\n15 13 15 15 12\n', '5 4\n15 13 15 15 12\n', '4 4\n20 10 40 30\n']

Demo Output:
['YES\n1 2 5 \n', 'NO\n', 'YES\n1 2 3 4 \n']

Note:
All possible answers for the first example: 
 -  {1 2 5} -  {2 3 5} -  {2 4 5} 
Note that the order does not matter.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jim is doing his discrete maths homework which requires him to repeatedly calculate ^{n}C_{r}(n choose r) for different values of n. Knowing that this is time consuming, he goes to his sister June for help. June,  being a computer science student knows how to convert this into a computer program and generate the answers quickly. She tells him, by storing the lower values of ^{n}C_{r}(n choose r), one can calculate the higher values using a very simple formula. 

If you are June, how will you calculate ^{n}C_{r} values for different values of n?

Since ${}^{n}C_{r}$values will be large you have to calculate them modulo $\mathbf{10^{9}}$.  

Input Format 

The first line contains the number of test cases T. 

T lines follow each containing an integer n. 

Output Format 

For each n output the list of ^{n}C_{0} to ^{n}C_{n} each separated by a single space in a new line. If the number is large, print only the last 9 digits. i.e. modulo 10^{9}

Constraints 

1<=T<=200 

1<=n< 1000

Sample Input

3
2
4
5

Sample Output

1 2 1
1 4 6 4 1
1 5 10 10 5 1

Explanation 

For 2 we can check ^{2}C_{0}  ^{2}C_{1} and ^{2}C_{2} are 1, 2 and 1 respectively. The other inputs' answer follow similar pattern.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We call two numbers $x$ and $y$ similar if they have the same parity (the same remainder when divided by $2$), or if $|x-y|=1$. For example, in each of the pairs $(2, 6)$, $(4, 3)$, $(11, 7)$, the numbers are similar to each other, and in the pairs $(1, 4)$, $(3, 12)$, they are not.

You are given an array $a$ of $n$ ($n$ is even) positive integers. Check if there is such a partition of the array into pairs that each element of the array belongs to exactly one pair and the numbers in each pair are similar to each other.

For example, for the array $a = [11, 14, 16, 12]$, there is a partition into pairs $(11, 12)$ and $(14, 16)$. The numbers in the first pair are similar because they differ by one, and in the second pair because they are both even.


-----Input-----

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

Each test case consists of two lines.

The first line contains an even positive integer $n$ ($2 \le n \le 50$) — length of array $a$.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$).


-----Output-----

For each test case print:  YES if the such a partition exists,  NO otherwise. 

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


-----Example-----
Input
7
4
11 14 16 12
2
1 8
4
1 1 1 1
4
1 2 5 6
2
12 13
6
1 6 3 10 5 8
6
1 12 3 10 5 8

Output
YES
NO
YES
YES
YES
YES
NO



-----Note-----

The first test case was explained in the statement.

In the second test case, the two given numbers are not similar.

In the third test case, any partition is suitable.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an undirected graph that consists of *n* vertices and *m* edges. Initially, each edge is colored either red or blue. Each turn a player picks a single vertex and switches the color of all edges incident to it. That is, all red edges with an endpoint in this vertex change the color to blue, while all blue edges with an endpoint in this vertex change the color to red.

Find the minimum possible number of moves required to make the colors of all edges equal.

Input Specification:
The first line of the input contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100<=000) — the number of vertices and edges, respectively.

The following *m* lines provide the description of the edges, as the *i*-th of them contains two integers *u**i* and *v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*, *u**i*<=≠<=*v**i*) — the indices of the vertices connected by the *i*-th edge, and a character *c**i* () providing the initial color of this edge. If *c**i* equals 'R', then this edge is initially colored red. Otherwise, *c**i* is equal to 'B' and this edge is initially colored blue. It's guaranteed that there are no self-loops and multiple edges.

Output Specification:
If there is no way to make the colors of all edges equal output <=-<=1 in the only line of the output. Otherwise first output *k* — the minimum number of moves required to achieve the goal, then output *k* integers *a*1,<=*a*2,<=...,<=*a**k*, where *a**i* is equal to the index of the vertex that should be used at the *i*-th move.

If there are multiple optimal sequences of moves, output any of them.

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

Demo Output:
['1\n2 \n', '2\n3 4 \n', '-1\n']

Note:
none

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