vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There is a universal library, where there is a big waiting room with seating capacity for maximum $m$ people, each of whom completes reading $n$ books sequentially. Reading each book requires one unit of time. 
Unfortunately, reading service is provided sequentially. After all of the $m$ people enter the library, the entrance gate is closed. There is only one reading table. So when someone reads, others have to wait in the waiting room. 
At first everybody chooses $n$ books they want to read. It takes $x$ amount of time. People can choose books simultaneously. Then they enter the waiting room. After reading $n$ books the person leaves the library immediately. 
As nothing is free, the cost of reading is also not free. If a person stays in the library $t$ units of time then the cost of reading is $\left \lfloor \frac{t-n}{m} \right \rfloor$ units of money. So, the $i^{th}$ person pays for time $x$ he needs to choose books and the time $(i-1)*n$ he needs to wait for all the persons before him to complete reading.
Note: $\left \lfloor a \right \rfloor$ denotes the floor($a$).

-----Input-----
- Each case contains three space-separated positive integers $n$, $m$ and $x$ where $n, x \leq 1000$ and $m \leq 10^{15}$. 
- End of input is determined by three zeros. 
- There are no more than 1000 test cases.

-----Output-----
- For each case, output in a single line the total unit of money the library gets in that day.

-----Sample Input-----
1 100 9
11 2 10
12 2 11
0 0 0

-----Sample Output-----
9
15
16

-----Explanation:-----
Testcase 2: Here, $n=11$, $m=2$, $x=10$.
For 1st person, 
$t=21$ and he/she gives $\left \lfloor \frac{21-11}{2} \right \rfloor = 5$ units of money.
For 2nd person,
$t=32$ and he/she gives $\left \lfloor \frac{32-11}{2} \right \rfloor= 10$ units of money.
So, total units of money $= 5+10 = 15$

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got an *n*<=×<=*m* matrix. The matrix consists of integers. In one move, you can apply a single transformation to the matrix: choose an arbitrary element of the matrix and increase it by 1. Each element can be increased an arbitrary number of times.

You are really curious about prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors: itself and number one. For example, numbers 2, 3, 5 are prime and numbers 1, 4, 6 are not. 

A matrix is prime if at least one of the two following conditions fulfills:
 -  the matrix has a row with prime numbers only; -  the matrix has a column with prime numbers only; 
Your task is to count the minimum number of moves needed to get a prime matrix from the one you've got.

Input Specification:
The first line contains two integers *n*,<=*m* (1<=≤<=*n*,<=*m*<=≤<=500) — the number of rows and columns in the matrix, correspondingly.

Each of the following *n* lines contains *m* integers — the initial matrix. All matrix elements are positive integers. All numbers in the initial matrix do not exceed 105.

The numbers in the lines are separated by single spaces.

Output Specification:
Print a single integer — the minimum number of moves needed to get a prime matrix from the one you've got. If you've got a prime matrix, print 0.

Demo Input:
['3 3\n1 2 3\n5 6 1\n4 4 1\n', '2 3\n4 8 8\n9 2 9\n', '2 2\n1 3\n4 2\n']

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

Note:
In the first sample you need to increase number 1 in cell (1, 1). Thus, the first row will consist of prime numbers: 2, 2, 3.

In the second sample you need to increase number 8 in cell (1, 2) three times. Thus, the second column will consist of prime numbers: 11, 2.

In the third sample you don't have to do anything as the second column already consists of prime numbers: 3, 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string, remove spaces from it. 
Example 1:
Input:
S = "geeks  for geeks"
Output: geeksforgeeks
Explanation: All the spaces have been 
removed.
Example 2:
Input: 
S = "    g f g"
Output: gfg
Explanation: All the spaces including
the leading ones have been removed.
Your Task:
You don't need to read input or print anything. Your task is to complete the function modify() which takes the string S as input and returns the resultant string by removing all the white spaces from S.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1<=|S|<=10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a toy building consisting of $n$ towers. Each tower consists of several cubes standing on each other. The $i$-th tower consists of $h_i$ cubes, so it has height $h_i$.

Let's define operation slice on some height $H$ as following: for each tower $i$, if its height is greater than $H$, then remove some top cubes to make tower's height equal to $H$. Cost of one "slice" equals to the total number of removed cubes from all towers.

Let's name slice as good one if its cost is lower or equal to $k$ ($k \ge n$).

 [Image] 

Calculate the minimum number of good slices you have to do to make all towers have the same height. Of course, it is always possible to make it so.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $n \le k \le 10^9$) — the number of towers and the restriction on slices, respectively.

The second line contains $n$ space separated integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 2 \cdot 10^5$) — the initial heights of towers.


-----Output-----

Print one integer — the minimum number of good slices you have to do to make all towers have the same heigth.


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

Output
2

Input
4 5
2 3 4 5

Output
2



-----Note-----

In the first example it's optimal to make $2$ slices. The first slice is on height $2$ (its cost is $3$), and the second one is on height $1$ (its cost is $4$).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Most of you have played card games (and if you haven’t, why not???) in which the deck of cards is randomized by shuffling it one or more times.

A perfect shuffle  is a type of shuffle where the initial deck is divided exactly in half, and the two halves are perfectly interleaved. For example, a deck consisting of eight cards ABCDEFGH (where A is the top card of the deck) would be divided into two halves ABCD and EFGH and then interleaved to get AEBFCGDH. Note that in this shuffle the original top card (A) stays on top — this type of perfect shuffle is called an out-shuffle. An equally valid perfect shuffle would start with the first card from the second half and result in EAFBGCHD — this is known as an in-shuffle.

While normal shuffling does a good job at randomizing a deck, perfect shuffles result in only a small number of possible orderings. For example, if we perform multiple out-shuffles on the deck above, we obtain the following: ABCDEFGH $\rightarrow $ AEBFCGDH $\rightarrow $ ACEGBDFH $\rightarrow $ ABCDEFGH $\rightarrow \cdots $

So after 3 out-shuffles, the deck is returned to its original state. A similar thing happens if we perform multiple in-shuffles on an 8-card deck, though in this case it would take 6 shuffles before we get back to where we started. With a standard 52 card deck, only 8 out-shuffles are needed before the deck is returned to its original order (talented magicians can make use of this result in many of their tricks). These shuffles can also be used on decks with an odd number of cards, but we have to be a little careful: for out-shuffles, the first half of the deck must have 1 more card than the second half; for in-shuffles, it’s the exact opposite. For example, an out-shuffle on the deck ABCDE results in ADBEC, while an in-shuffle results in CADBE.

For this problem you will be given the size of a deck and must determine how many in- or out-shuffles it takes to return the deck to its pre-shuffled order.

-----Input-----
The input consists of one line containing a positive integer $n \leq 1000$ (the size of the deck) followed by either the word in or out, indicating whether you should perform in-shuffles or out-shuffles.

-----Output-----
For each test case, output the case number followed by the number of in- or out-shuffles required to return the deck to its original order.

-----Examples-----
Sample Input 1:
8 out
Sample Output 1:
3

Sample Input 2:
8 in
Sample Output 2:
6

Sample Input 3:
52 out
Sample Output 3:
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is having one string of English lower case alphabets only. The chef wants to remove all "abc" special pairs where a,b,c are occurring consecutively. After removing the pair, create a new string and again remove "abc" special pair from a newly formed string. Repeate the process until no such pair remains in a string.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, $String$. 

-----Output:-----
For each testcase, output in a single line answer, new String with no "abc" special pair.

-----Constraints:-----
$T \leq 2 $
$1 \leq String length \leq 1000 $

-----Sample Input:-----
2
aabcc
bababccc

-----Sample Output:-----
ac
bc

-----EXPLANATION:-----
For 1) after removing "abc" at middle we get a new string as ac.
For 2) string = bababccc
newString1 = babcc  // After removing middle "abc"
newString2 = bc   //After removing "abc"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chess knight has a unique movement, it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L). The possible movements of chess knight are shown in this diagaram:
A chess knight can move as indicated in the chess diagram below:

We have a chess knight and a phone pad as shown below, the knight can only stand on a numeric cell (i.e. blue cell).

Given an integer n, return how many distinct phone numbers of length n we can dial.
You are allowed to place the knight on any numeric cell initially and then you should perform n - 1 jumps to dial a number of length n. All jumps should be valid knight jumps.
As the answer may be very large, return the answer modulo 109 + 7.
 
Example 1:
Input: n = 1
Output: 10
Explanation: We need to dial a number of length 1, so placing the knight over any numeric cell of the 10 cells is sufficient.

Example 2:
Input: n = 2
Output: 20
Explanation: All the valid number we can dial are [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

Example 3:
Input: n = 3
Output: 46

Example 4:
Input: n = 4
Output: 104

Example 5:
Input: n = 3131
Output: 136006598
Explanation: Please take care of the mod.

 
Constraints:

1 <= n <= 5000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice has a cute cat. To keep her cat fit, Alice wants to design an exercising walk for her cat! 

Initially, Alice's cat is located in a cell $(x,y)$ of an infinite grid. According to Alice's theory, cat needs to move:   exactly $a$ steps left: from $(u,v)$ to $(u-1,v)$;  exactly $b$ steps right: from $(u,v)$ to $(u+1,v)$;  exactly $c$ steps down: from $(u,v)$ to $(u,v-1)$;  exactly $d$ steps up: from $(u,v)$ to $(u,v+1)$. 

Note that the moves can be performed in an arbitrary order. For example, if the cat has to move $1$ step left, $3$ steps right and $2$ steps down, then the walk right, down, left, right, right, down is valid.

Alice, however, is worrying that her cat might get lost if it moves far away from her. So she hopes that her cat is always in the area $[x_1,x_2]\times [y_1,y_2]$, i.e. for every cat's position $(u,v)$ of a walk $x_1 \le u \le x_2$ and $y_1 \le v \le y_2$ holds.

Also, note that the cat can visit the same cell multiple times.

Can you help Alice find out if there exists a walk satisfying her wishes?

Formally, the walk should contain exactly $a+b+c+d$ unit moves ($a$ to the left, $b$ to the right, $c$ to the down, $d$ to the up). Alice can do the moves in any order. Her current position $(u, v)$ should always satisfy the constraints: $x_1 \le u \le x_2$, $y_1 \le v \le y_2$. The staring point is $(x, y)$.

You are required to answer $t$ test cases independently.


-----Input-----

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

The first line of each test case contains four integers $a$, $b$, $c$, $d$ ($0 \le a,b,c,d \le 10^8$, $a+b+c+d \ge 1$).

The second line of the test case contains six integers $x$, $y$, $x_1$, $y_1$, $x_2$, $y_2$ ($-10^8 \le x_1\le x \le x_2 \le 10^8$, $-10^8 \le y_1 \le y \le y_2 \le 10^8$).


-----Output-----

For each test case, output "YES" in a separate line, if there exists a walk satisfying her wishes. Otherwise, output "NO" in a separate line. 

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


-----Example-----
Input
6
3 2 2 2
0 0 -2 -2 2 2
3 1 4 1
0 0 -1 -1 1 1
1 1 1 1
1 1 1 1 1 1
0 0 0 1
0 0 0 0 0 1
5 1 1 1
0 0 -100 -100 0 100
1 1 5 1
0 0 -100 -100 100 0

Output
Yes
No
No
Yes
Yes
Yes



-----Note-----

In the first test case, one valid exercising walk is $$(0,0)\rightarrow (-1,0) \rightarrow (-2,0)\rightarrow (-2,1) \rightarrow (-2,2)\rightarrow (-1,2)\rightarrow(0,2)\rightarrow (0,1)\rightarrow (0,0) \rightarrow (-1,0)$$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monkeys in the army were fascinated by a game which people of Lanka used to play. It consist of forming Anagrams of a string of letters. An anagram is a string formed by rearranging the letters of a given string. For example one of the anagram of "elvis" is "lives".

You will be provided with two string 's' and 't'. You can insert letters in string 's' so that string 't' is one of the Anagram of the newly formed string (after insertion in 's').

Your job is to count the number of unique letter insertions made if possible otherwise print -1. For example if 'a' is inserted thrice then it will counted as 1.
String will only consist of lower case letters ('a' - 'z').

Input:

First line will contain T ,denoting the number of test cases.
Each test case  will consist of two lines. First line will contain string s and next line will contain string t.

Ouput:

Output the required answer in new line.

Constraint:

0  <  T  < =20

0 < |s| ≤ 1000

0 < |t| ≤ 1000

|s| ≤ |t|

where, |s| denotes the length of the string s.

Note: You can insert letter(s) anywhere in the string 's'.

SAMPLE INPUT
2
a
agh

ankur
durgesh

SAMPLE OUTPUT
2
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set of points on a straight line. Each point has a color assigned to it. For point a, its neighbors are the points which don't have any other points between them and a. Each point has at most two neighbors - one from the left and one from the right.

You perform a sequence of operations on this set of points. In one operation, you delete all points which have a neighbor point of a different color than the point itself. Points are deleted simultaneously, i.e. first you decide which points have to be deleted and then delete them. After that you can perform the next operation etc. If an operation would not delete any points, you can't perform it.

How many operations will you need to perform until the next operation does not have any points to delete?


-----Input-----

Input contains a single string of lowercase English letters 'a'-'z'. The letters give the points' colors in the order in which they are arranged on the line: the first letter gives the color of the leftmost point, the second gives the color of the second point from the left etc.

The number of the points is between 1 and 10^6.


-----Output-----

Output one line containing an integer - the number of operations which can be performed on the given set of points until there are no more points to delete.


-----Examples-----
Input
aabb

Output
2

Input
aabcaa

Output
1



-----Note-----

In the first test case, the first operation will delete two middle points and leave points "ab", which will be deleted with the second operation. There will be no points left to apply the third operation to.

In the second test case, the first operation will delete the four points in the middle, leaving points "aa". None of them have neighbors of other colors, so the second operation can't be applied.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is given a positive integer $n$. In $1$ move, one can select any single digit and remove it (i.e. one selects some position in the number and removes the digit located at this position). The operation cannot be performed if only one digit remains. If the resulting number contains leading zeroes, they are automatically removed.

E.g. if one removes from the number $32925$ the $3$-rd digit, the resulting number will be $3225$. If one removes from the number $20099050$ the first digit, the resulting number will be $99050$ (the $2$ zeroes going next to the first digit are automatically removed).

What is the minimum number of steps to get a number such that it is divisible by $25$ and positive? It is guaranteed that, for each $n$ occurring in the input, the answer exists. It is guaranteed that the number $n$ has no leading zeros.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case consists of one line containing one integer $n$ ($25 \le n \le 10^{18}$). It is guaranteed that, for each $n$ occurring in the input, the answer exists. It is guaranteed that the number $n$ has no leading zeros.


-----Output-----

For each test case output on a separate line an integer $k$ ($k \ge 0$) — the minimum number of steps to get a number such that it is divisible by $25$ and positive.


-----Examples-----

Input
5
100
71345
3259
50555
2050047
Output
0
3
1
3
2


-----Note-----

In the first test case, it is already given a number divisible by $25$.

In the second test case, we can remove the digits $1$, $3$, and $4$ to get the number $75$.

In the third test case, it's enough to remove the last digit to get the number $325$.

In the fourth test case, we can remove the three last digits to get the number $50$.

In the fifth test case, it's enough to remove the digits $4$ and $7$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree with N vertices numbered 1, 2, ..., N. The i-th edge connects Vertex a_i and Vertex b_i. You are also given a string S of length N consisting of `0` and `1`. The i-th character of S represents the number of pieces placed on Vertex i.

Snuke will perform the following operation some number of times:

* Choose two pieces the distance between which is at least 2, and bring these pieces closer to each other by 1. More formally, choose two vertices u and v, each with one or more pieces, and consider the shortest path between them. Here the path must contain at least two edges. Then, move one piece from u to its adjacent vertex on the path, and move one piece from v to its adjacent vertex on the path.



By repeating this operation, Snuke wants to have all the pieces on the same vertex. Is this possible? If the answer is yes, also find the minimum number of operations required to achieve it.

Constraints

* 2 \leq N \leq 2000
* |S| = N
* S consists of `0` and `1`, and contains at least one `1`.
* 1 \leq a_i, b_i \leq N(a_i \neq b_i)
* The edges (a_1, b_1), (a_2, b_2), ..., (a_{N - 1}, b_{N - 1}) forms a tree.

Input

Input is given from Standard Input in the following format:


N
S
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}


Output

If it is impossible to have all the pieces on the same vertex, print `-1`. If it is possible, print the minimum number of operations required.

Examples

Input

7
0010101
1 2
2 3
1 4
4 5
1 6
6 7


Output

3


Input

7
0010110
1 2
2 3
1 4
4 5
1 6
6 7


Output

-1


Input

2
01
1 2


Output

0

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A map of some object is a rectangular field consisting of *n* rows and *n* columns. Each cell is initially occupied by the sea but you can cover some some cells of the map with sand so that exactly *k* islands appear on the map. We will call a set of sand cells to be island if it is possible to get from each of them to each of them by moving only through sand cells and by moving from a cell only to a side-adjacent cell. The cells are called to be side-adjacent if they share a vertical or horizontal side. It is easy to see that islands do not share cells (otherwise they together form a bigger island).

Find a way to cover some cells with sand so that exactly *k* islands appear on the *n*<=×<=*n* map, or determine that no such way exists.

Input Specification:
The single line contains two positive integers *n*, *k* (1<=≤<=*n*<=≤<=100, 0<=≤<=*k*<=≤<=*n*2) — the size of the map and the number of islands you should form.

Output Specification:
If the answer doesn't exist, print "NO" (without the quotes) in a single line.

Otherwise, print "YES" in the first line. In the next *n* lines print the description of the map. Each of the lines of the description must consist only of characters 'S' and 'L', where 'S' is a cell that is occupied by the sea and 'L' is the cell covered with sand. The length of each line of the description must equal *n*.

If there are multiple answers, you may print any of them.

You should not maximize the sizes of islands.

Demo Input:
['5 2\n', '5 25\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given one polygonal line, which is a collection of line segments. Your task is to calculate the sum of areas enclosed by the polygonal line.

A point is defined to be "enclosed" if and only if the point is unreachable without crossing at least one line segment from the point at infinity.



Input

The first line contains one integers N (2 ≤ N ≤ 100). N is the number of segments.

Each of the following N lines consists of two integers Xi and Yi (-105 ≤ Xi, Yi ≤ 105, 1 ≤ i ≤ N) which represents a vertex. A polygonal line is the segments which connect (Xj, Yj) and (Xj+1, Yj+1) ((Xj, Yj) ≠ (Xj+1, Yj+1), 1 ≤ j ≤ N-1). The distance between a segment Sj and all vertices except the end points on segment Sj is guaranteed to be greater than 0.01.

Output

Output the answer in a line. The answer may be printed with an arbitrary number of decimal digits, but may not contain an absolute or relative error greater than or equal to 10-6.

Examples

Input

5
0 0
1 1
1 0
0 1
0 0


Output

0.5


Input

5
0 0
1 1
1 0
0 1
1 0


Output

0.25


Input

21
1 1
-1 1
-1 2
-2 2
-2 1
-1 1
-1 -1
-2 -1
-2 -2
-1 -2
-1 -1
1 -1
1 -2
2 -2
2 -1
1 -1
1 1
2 1
2 2
1 2
1 1


Output

8


Input

16
0 0
1 0
1 1
0 1
0 2
0 3
1 3
1 2
2 2
2 3
3 3
3 2
3 1
2 1
2 0
3 0


Output

0


Input

7
26 52
33 12
-51 68
16 61
43 -26
87 24
12 10


Output

2714.840579710

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