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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Petya likes arrays of integers a lot. Recently his mother has presented him one such array consisting of *n* elements. Petya is now wondering whether he can swap any two distinct integers in the array so that the array got unsorted. Please note that Petya can not swap equal integers even if they are in distinct positions in the array. Also note that Petya must swap some two integers even if the original array meets all requirements.

Array *a* (the array elements are indexed from 1) consisting of *n* elements is called sorted if it meets at least one of the following two conditions:
 1.  *a*1<=≤<=*a*2<=≤<=...<=≤<=*a**n*; 1.  *a*1<=≥<=*a*2<=≥<=...<=≥<=*a**n*. 
Help Petya find the two required positions to swap or else say that they do not exist.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=105). The second line contains *n* non-negative space-separated integers *a*1,<=*a*2,<=...,<=*a**n* — the elements of the array that Petya's mother presented him. All integers in the input do not exceed 109.

Output Specification:
If there is a pair of positions that make the array unsorted if swapped, then print the numbers of these positions separated by a space. If there are several pairs of positions, print any of them. If such pair does not exist, print -1. The positions in the array are numbered with integers from 1 to *n*.

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

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

Note:
In the first two samples the required pairs obviously don't exist.

In the third sample you can swap the first two elements. After that the array will look like this: 2 1 3 4. This array is unsorted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have managed to intercept an important message and you are trying to read it.

You realise that the message has been encoded and can be decoded by switching each letter with a corresponding letter.

You also notice that each letter is paired with the letter that it coincides with when the alphabet is reversed.

For example: "a" is encoded with "z", "b" with "y", "c" with "x", etc

You read the first sentence:
```
"r slkv mlylwb wvxlwvh gsrh nvhhztv"
```

After a few minutes you manage to decode it:
```
"i hope nobody decodes this message"
```
Create a function that will instantly decode any of these messages

You can assume no punctuation or capitals, only lower case letters, but remember spaces!

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


Your are given a string. You must replace the word(s) `coverage` by `covfefe`, however, if you don't find the word `coverage` in the string, you must add `covfefe` at the end of the string with a leading space.

For the languages where the string is not immutable (such as ruby), don't modify the given string, otherwise this will break the test cases.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are working as an analyst in a company working on a new system for big data storage. This system will store n different objects. Each object should have a unique ID.

To create the system, you choose the parameters of the system — integers m ≥ 1 and b_{1}, b_{2}, …, b_{m}. With these parameters an ID of some object in the system is an array of integers [a_{1}, a_{2}, …, a_{m}] where 1 ≤ a_{i} ≤ b_{i} holds for every 1 ≤ i ≤ m.

Developers say that production costs are proportional to ∑_{i=1}^{m} b_{i}. You are asked to choose parameters m and b_{i} so that the system will be able to assign unique IDs to n different objects and production costs are minimized. Note that you don't have to use all available IDs.

Input

In the only line of input there is one positive integer n. The length of the decimal representation of n is no greater than 1.5 ⋅ 10^{6}. The integer does not contain leading zeros.

Output

Print one number — minimal value of ∑_{i=1}^{m} b_{i}.

Examples

Input

36


Output

10


Input

37


Output

11


Input

12345678901234567890123456789


Output

177

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan unexpectedly saw a present from one of his previous birthdays. It is array of $n$ numbers from $1$ to $200$. Array is old and some numbers are hard to read. Ivan remembers that for all elements at least one of its neighbours ls not less than it, more formally:

$a_{1} \le a_{2}$,

$a_{n} \le a_{n-1}$ and

$a_{i} \le max(a_{i-1}, \,\, a_{i+1})$ for all $i$ from $2$ to $n-1$.

Ivan does not remember the array and asks to find the number of ways to restore it. Restored elements also should be integers from $1$ to $200$. Since the number of ways can be big, print it modulo $998244353$.


-----Input-----

First line of input contains one integer $n$ ($2 \le n \le 10^{5}$) — size of the array.

Second line of input contains $n$ integers $a_{i}$ — elements of array. Either $a_{i} = -1$ or $1 \le a_{i} \le 200$. $a_{i} = -1$ means that $i$-th element can't be read.


-----Output-----

Print number of ways to restore the array modulo $998244353$.


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

Output
1

Input
2
-1 -1

Output
200



-----Note-----

In the first example, only possible value of $a_{2}$ is $2$.

In the second example, $a_{1} = a_{2}$ so there are $200$ different values because all restored elements should be integers between $1$ and $200$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Petya walked in the forest and found a magic stick.

Since Petya really likes numbers, the first thing he learned was spells for changing numbers. So far, he knows only two spells that can be applied to a positive integer:   If the chosen number $a$ is even, then the spell will turn it into $\frac{3a}{2}$;  If the chosen number $a$ is greater than one, then the spell will turn it into $a-1$. 

Note that if the number is even and greater than one, then Petya can choose which spell to apply.

Petya now has only one number $x$. He wants to know if his favorite number $y$ can be obtained from $x$ using the spells he knows. The spells can be used any number of times in any order. It is not required to use spells, Petya can leave $x$ as it is.


-----Input-----

The first line contains single integer $T$ ($1 \le T \le 10^4$) — the number of test cases. Each test case consists of two lines.

The first line of each test case contains two integers $x$ and $y$ ($1 \le x, y \le 10^9$) — the current number and the number that Petya wants to get.


-----Output-----

For the $i$-th test case print the answer on it — YES if Petya can get the number $y$ from the number $x$ using known spells, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).


-----Example-----
Input
7
2 3
1 1
3 6
6 8
1 2
4 1
31235 6578234

Output
YES
YES
NO
YES
NO
YES
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Define a method that accepts 2 strings as parameters. The method returns the first string sorted by the second.

```python
sort_string("foos", "of")       == "oofs"
sort_string("string", "gnirts") == "gnirts"
sort_string("banana", "abn")    == "aaabnn"
```

To elaborate, the second string defines the ordering. It is possible that in the second string characters repeat, so you should remove repeating characters, leaving only the first occurrence.

Any character in the first string that does not appear in the second string should be sorted to the end of the result in original order.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem is an extension of another Kattis problem - backspace. In that problem, every time we see a character ‘<’, it actually means that the ‘Backspace’ key is pressed and we undo the last character that was just typed.


The extension is as follows: Now, pressing a ‘<’ (the ‘Backspace’ key) when the (typing) cursor is at the front of the line does nothing. Now if we see a character ‘[’, it actually means that the ‘Home’ key is pressed and we move the (typing) cursor to the front of the line. Similarly, if we see a character ‘]’, it actually means that the ‘End’ key is pressed and we move the (typing) cursor the back of the line. For all other valid character in the input, it actually means that the corresponding key is pressed, we insert that character at the (typing) cursor position, and advance one position to the right the cursor accordingly.

-----Input-----
The input starts with a line containing just one integer $T \: (1 \le T \le 10)$, denoting the number of test cases.


Each test case is a line containing the string that was written in the Text Editor Sim (Steven IMproved). The length of the string is at most $10^{6}$, and it will only contain lowercase letters from the English alphabet [‘$a$’$\; \ldots \; $‘$z$’], digits [‘$0$’$\; \ldots \; $‘$9$’], spaces, as well as some of the three special characters: ‘<’, ‘[’, or ‘]’.

-----Output-----
For each test case, output one line containing the final string that is displayed on screen.

-----Subtasks-----
 - $\textbf{(27.5 points)}$: $1 \le T \le 10$, string length is at most $10^{3}$, there is no ‘[’, as seen in sample $1$.
 - $\textbf{(32.5 points)}$: $1 \le T \le 10$, string length is at most $10^{3}$, there may be ‘[’, as seen in sample $2$.
 - $\textbf{(40 points)}$: $1 \le T \le 4$, string length is at most $10^{6}$.

-----Examples-----
Sample Input:
1
my ]]name]] is]] steva<en]<n halim]]]]]
Sample Output:
my name is steven halim

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given non-negative integer N. Find N pairwise different points on the Euclidean plane with integer coordinates in the corresponding order and the following properties: 
1) the distance between any two consecutive points in the order is equal for the all  pairs of consecutive points 2) the angle created by any three consecutive points in the order is equal for the all triples of consecutive points.
The last and the first point in the order are considered consecutive.

Input 
The first line contains one integer N (0 < N ≤ 100) 

Output
Output "NO" if it's impossible to find such N points. Otherwise output "YES" and then N lines describing points - one point per line. Each point is described by 2 space-separated integers - its coordinates. Among all possible solutions you should choose the one with the least distance between consecutive points. The point with the lowest first coordinate (among all of them with the lowest second coordinate) should have coordinates (0, 0). If there are still more than one solution you should choose the one with the highest point to be as low as possible.

SAMPLE INPUT
4

SAMPLE OUTPUT
YES
0 0
0 1
1 1
1 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A small country called Maltius was governed by a queen. The queen was known as an oppressive ruler. People in the country suffered from heavy taxes and forced labor. So some young people decided to form a revolutionary army and fight against the queen. Now, they besieged the palace and have just rushed into the entrance.

Your task is to write a program to determine whether the queen can escape or will be caught by the army.

Here is detailed description.

* The palace can be considered as grid squares.
* The queen and the army move alternately. The queen moves first.
* At each of their turns, they either move to an adjacent cell or stay at the same cell.
* Each of them must follow the optimal strategy.
* If the queen and the army are at the same cell, the queen will be caught by the army immediately.
* If the queen is at any of exit cells alone after the army’s turn, the queen can escape from the army.
* There may be cases in which the queen cannot escape but won’t be caught by the army forever, under their optimal strategies.

Hint

On the first sample input, the queen can move to exit cells, but either way the queen will be caught at the next army’s turn. So the optimal strategy for the queen is staying at the same cell. Then the army can move to exit cells as well, but again either way the army will miss the queen from the other exit. So the optimal strategy for the army is also staying at the same cell. Thus the queen cannot escape but won’t be caught.



Input

The input consists of multiple datasets. Each dataset describes a map of the palace. The first line of the input contains two integers W (1 ≤ W ≤ 30) and H (1 ≤ H ≤ 30), which indicate the width and height of the palace. The following H lines, each of which contains W characters, denote the map of the palace. "Q" indicates the queen, "A" the army,"E" an exit,"#" a wall and "." a floor.

The map contains exactly one "Q", exactly one "A" and at least one "E". You can assume both the queen and the army can reach all the exits.

The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.

Output

For each dataset, output "Queen can escape.", "Army can catch Queen." or "Queen can not escape and Army can not catch Queen." in a line.

Examples

Input

2 2
QE
EA
3 1
QAE
3 1
AQE
5 5
..E..
.###.
A###Q
.###.
..E..
5 1
A.E.Q
5 5
A....
####.
..E..
.####
....Q
0 0


Output

Queen can not escape and Army can not catch Queen.
Army can catch Queen.
Queen can escape.
Queen can not escape and Army can not catch Queen.
Army can catch Queen.
Army can catch Queen.


Input

2 2
QE
EA
3 1
QAE
3 1
AQE
5 5
..E..
.###.
A###Q
.###.
..E..
5 1
A.E.Q
5 5
A....
.
..E..
.####
....Q
0 0


Output

Queen can not escape and Army can not catch Queen.
Army can catch Queen.
Queen can escape.
Queen can not escape and Army can not catch Queen.
Army can catch Queen.
Army can catch Queen.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today is the judgment day of Pokemons worldcup and all the audience are waiting outside the stadium. Many families has come to see the world cup (say N). Each family has atleast one and atmost four members and they want to seat together. The sitting arrangement in the stadium is such that one   row can hold maximum four peoples. what is the minimum numbers of  rows required such that all the family members sit together ( in one row there can be more than one family ) ? 
Input:
First line of input contains T - total no. of test cases
Each test case is followed by two lines: 
First list  is N denoting total no of families 
Second line contains N space separated  integers S1,S2 ..... SN denoting size of family 

Output:
Print the single number — the minimum number of rows required.
Constraints: 
      1 ≤T ≤ 100 
     3 ≤ N ≤ 100 
    1 ≤ S1,S2 ..... SN ≤ 4

SAMPLE INPUT
2
5
1 2 4 3 3
8
2 3 4 4 2 1 3 1

SAMPLE OUTPUT
4
5

Explanation

In the first test case we can sort the families into 4 rows like this:
the third family (consisting of four members),
the fourth family (consisting of three members),
the fifth family(consisting of three members),
the first and the second family(consisting of one and two members, correspondingly).

There are other ways to sort the families into four rows.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an Integer N, write a program to reverse it.

-----Input-----

The first line contains an integer T, total number of testcases. Then follow T lines, each line contains an integer N. 

-----Output-----
For each test case, display the reverse of the given number N, in a new line.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 1000000

-----Example-----
Input
4
12345
31203
2123
2300
Output
54321
30213
3212
32

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef Monocarp has just put $n$ dishes into an oven. He knows that the $i$-th dish has its optimal cooking time equal to $t_i$ minutes.

At any positive integer minute $T$ Monocarp can put no more than one dish out of the oven. If the $i$-th dish is put out at some minute $T$, then its unpleasant value is $|T - t_i|$ — the absolute difference between $T$ and $t_i$. Once the dish is out of the oven, it can't go back in.

Monocarp should put all the dishes out of the oven. What is the minimum total unpleasant value Monocarp can obtain?


-----Input-----

The first line contains a single integer $q$ ($1 \le q \le 200$) — the number of testcases.

Then $q$ testcases follow.

The first line of the testcase contains a single integer $n$ ($1 \le n \le 200$) — the number of dishes in the oven.

The second line of the testcase contains $n$ integers $t_1, t_2, \dots, t_n$ ($1 \le t_i \le n$) — the optimal cooking time for each dish.

The sum of $n$ over all $q$ testcases doesn't exceed $200$.


-----Output-----

Print a single integer for each testcase — the minimum total unpleasant value Monocarp can obtain when he puts out all the dishes out of the oven. Remember that Monocarp can only put the dishes out at positive integer minutes and no more than one dish at any minute.


-----Example-----
Input
6
6
4 2 4 4 5 2
7
7 7 7 7 7 7 7
1
1
5
5 1 2 4 3
4
1 4 4 4
21
21 8 1 4 1 5 21 1 8 21 11 21 11 3 12 8 19 15 9 11 13

Output
4
12
0
0
2
21



-----Note-----

In the first example Monocarp can put out the dishes at minutes $3, 1, 5, 4, 6, 2$. That way the total unpleasant value will be $|4 - 3| + |2 - 1| + |4 - 5| + |4 - 4| + |6 - 5| + |2 - 2| = 4$.

In the second example Monocarp can put out the dishes at minutes $4, 5, 6, 7, 8, 9, 10$.

In the third example Monocarp can put out the dish at minute $1$.

In the fourth example Monocarp can put out the dishes at minutes $5, 1, 2, 4, 3$.

In the fifth example Monocarp can put out the dishes at minutes $1, 3, 4, 5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A new town is being planned, and the designers have some very specific ideas about how things should be laid out. First, they lay out the streets. Each street is perfectly straight and passes completely from one end of the town to the other. These streets divide the town into regions, and each region is to be designated either “residential” or “commercial.” The town planners require that any two regions directly across the street from one another must have different designations. On this one particular day, all of the streets have been planned, but none of the regions have been designated. One town planner wishes to purchase two properties, and it is important to him that the properties eventually have different designations. For this problem, the streets can be modeled by lines in the plane that extend forever in both directions and have no width, and properties may be modeled by points. Given the lines and two points, can you decide whether or not they must get different designations, “commercial” or “residential?” 

-----Input-----
Input begins with an integer $S$ on a single line, giving the number of streets ($1 \le S \le 10000$). The next $S$ lines of input each contain four integers $x_1$, $y_1$, $x_2$, and $y_2$, specifying the coordinates of two distinct points $(x_1, y_1)$ and $(x_2, y_2)$. The unique line through these two points gives one of the streets. Each coordinate is in the range $[0, 10000]$, and no two lines will be identical. That is, the town will have $S$ distinct streets. The next line contains an integer $T$, the number of pairs of properties to test ($ 1 \le T \le 1000$). This is followed by $T$ lines of input, each containing four integers $x_3$, $y_3$, $x_4$, and $y_4$, representing two distinct points $(x_3, y_3)$ and $(x_4, y_4)$, where each point lies within one of the two properties to test. None of these points will lie on any of the streets, nor will both points lie within the same property. Again, each coordinate is in the range $[0, 10000]$.

-----Output-----
For each of the $T$ pairs of properties to be tested, output either “same” if the properties are guaranteed to receive the same designation or “different” if they are guaranteed to receive different designations.

-----Examples-----
Sample Input:
2
1 1 2 1
1 1 1 2
3
2 0 2 2
2 0 0 3
0 0 2 2
Sample Output:
different
same
same

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
What joy! Petya's parents went on a business trip for the whole year and the playful kid is left all by himself. Petya got absolutely happy. He jumped on the bed and threw pillows all day long, until... 

Today Petya opened the cupboard and found a scary note there. His parents had left him with duties: he should water their favourite flower all year, each day, in the morning, in the afternoon and in the evening. "Wait a second!" — thought Petya. He know for a fact that if he fulfills the parents' task in the *i*-th (1<=≤<=*i*<=≤<=12) month of the year, then the flower will grow by *a**i* centimeters, and if he doesn't water the flower in the *i*-th month, then the flower won't grow this month. Petya also knows that try as he might, his parents won't believe that he has been watering the flower if it grows strictly less than by *k* centimeters. 

Help Petya choose the minimum number of months when he will water the flower, given that the flower should grow no less than by *k* centimeters.

Input Specification:
The first line contains exactly one integer *k* (0<=≤<=*k*<=≤<=100). The next line contains twelve space-separated integers: the *i*-th (1<=≤<=*i*<=≤<=12) number in the line represents *a**i* (0<=≤<=*a**i*<=≤<=100).

Output Specification:
Print the only integer — the minimum number of months when Petya has to water the flower so that the flower grows no less than by *k* centimeters. If the flower can't grow by *k* centimeters in a year, print -1.

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

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

Note:
Let's consider the first sample test. There it is enough to water the flower during the seventh and the ninth month. Then the flower grows by exactly five centimeters.

In the second sample Petya's parents will believe him even if the flower doesn't grow at all (*k* = 0). So, it is possible for Petya not to water the flower at all.

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