vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an integer $n$ from $1$ to $10^{18}$ without leading zeroes.

In one move you can swap any two adjacent digits in the given number in such a way that the resulting number will not contain leading zeroes. In other words, after each move the number you have cannot contain any leading zeroes.

What is the minimum number of moves you have to make to obtain a number that is divisible by $25$? Print -1 if it is impossible to obtain a number that is divisible by $25$.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^{18}$). It is guaranteed that the first (left) digit of the number $n$ is not a zero.


-----Output-----

If it is impossible to obtain a number that is divisible by $25$, print -1. Otherwise print the minimum number of moves required to obtain such number.

Note that you can swap only adjacent digits in the given number.


-----Examples-----
Input
5071

Output
4

Input
705

Output
1

Input
1241367

Output
-1



-----Note-----

In the first example one of the possible sequences of moves is 5071 $\rightarrow$ 5701 $\rightarrow$ 7501 $\rightarrow$ 7510 $\rightarrow$ 7150.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program which manipulates a sequence $A$ = {$a_0, a_1, ..., a_{n-1}$} with the following operations:

* $add(s, t, x)$ : add $x$ to $a_s, a_{s+1}, ..., a_t$.
* $find(s, t)$ : report the minimum value in $a_s, a_{s+1}, ..., a_t$.



Note that the initial values of $a_i ( i = 0, 1, ..., n-1 )$ are 0.

Constraints

* $1 ≤ n ≤ 100000$
* $1 ≤ q ≤ 100000$
* $0 ≤ s ≤ t < n$
* $-1000 ≤ x ≤ 1000$

Input


$n$ $q$
$query_1$
$query_2$
:
$query_q$


In the first line, $n$ (the number of elements in $A$) and $q$ (the number of queries) are given. Then, $i$th query $query_i$ is given in the following format:


0 $s$ $t$ $x$


or


1 $s$ $t$


The first digit represents the type of the query. '0' denotes $add(s, t, x)$ and '1' denotes $find(s, t)$.

Output

For each $find$ query, print the minimum value.

Example

Input

6 7
0 1 3 1
0 2 4 -2
1 0 5
1 0 1
0 3 5 3
1 3 4
1 0 5


Output

-2
0
1
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is November 18 now in Japan. By the way, 11 and 18 are adjacent Lucas numbers.

You are given an integer N. Find the N-th Lucas number.

Here, the i-th Lucas number L_i is defined as follows:

* L_0=2
* L_1=1
* L_i=L_{i-1}+L_{i-2} (i≥2)

Constraints

* 1≤N≤86
* It is guaranteed that the answer is less than 10^{18}.
* N is an integer.

Input

Input is given from Standard Input in the following format:


N


Output

Print the N-th Lucas number.

Examples

Input

5


Output

11


Input

86


Output

939587134549734843

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An X-layered kagami mochi (X ≥ 1) is a pile of X round mochi (rice cake) stacked vertically where each mochi (except the bottom one) has a smaller diameter than that of the mochi directly below it. For example, if you stack three mochi with diameters of 10, 8 and 6 centimeters from bottom to top in this order, you have a 3-layered kagami mochi; if you put just one mochi, you have a 1-layered kagami mochi.
Lunlun the dachshund has N round mochi, and the diameter of the i-th mochi is d_i centimeters. When we make a kagami mochi using some or all of them, at most how many layers can our kagami mochi have?

-----Constraints-----
 - 1 ≤ N ≤ 100
 - 1 ≤ d_i ≤ 100
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
d_1
:
d_N

-----Output-----
Print the maximum number of layers in a kagami mochi that can be made.

-----Sample Input-----
4
10
8
8
6

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

If we stack the mochi with diameters of 10, 8 and 6 centimeters from bottom to top in this order, we have a 3-layered kagami mochi, which is the maximum number of layers.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has a water bottle with the shape of a rectangular prism whose base is a square of side a~\mathrm{cm} and whose height is b~\mathrm{cm}. (The thickness of the bottle can be ignored.)

We will pour x~\mathrm{cm}^3 of water into the bottle, and gradually tilt the bottle around one of the sides of the base.

When will the water be spilled? More formally, find the maximum angle in which we can tilt the bottle without spilling any water.

Constraints

* All values in input are integers.
* 1 \leq a \leq 100
* 1 \leq b \leq 100
* 1 \leq x \leq a^2b

Input

Input is given from Standard Input in the following format:


a b x


Output

Print the maximum angle in which we can tilt the bottle without spilling any water, in degrees. Your output will be judged as correct when the absolute or relative error from the judge's output is at most 10^{-6}.

Examples

Input

2 2 4


Output

45.0000000000


Input

12 21 10


Output

89.7834636934


Input

3 1 8


Output

4.2363947991

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a colored permutation $p_1, p_2, \dots, p_n$. The $i$-th element of the permutation has color $c_i$.

Let's define an infinite path as infinite sequence $i, p[i], p[p[i]], p[p[p[i]]] \dots$ where all elements have same color ($c[i] = c[p[i]] = c[p[p[i]]] = \dots$).

We can also define a multiplication of permutations $a$ and $b$ as permutation $c = a \times b$ where $c[i] = b[a[i]]$. Moreover, we can define a power $k$ of permutation $p$ as $p^k=\underbrace{p \times p \times \dots \times p}_{k \text{ times}}$.

Find the minimum $k > 0$ such that $p^k$ has at least one infinite path (i.e. there is a position $i$ in $p^k$ such that the sequence starting from $i$ is an infinite path).

It can be proved that the answer always exists.


-----Input-----

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

Next $3T$ lines contain test cases — one per three lines. The first line contains single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the permutation.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i \neq p_j$ for $i \neq j$) — the permutation $p$.

The third line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$) — the colors of elements of the permutation.

It is guaranteed that the total sum of $n$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

Print $T$ integers — one per test case. For each test case print minimum $k > 0$ such that $p^k$ has at least one infinite path.


-----Example-----
Input
3
4
1 3 4 2
1 2 2 3
5
2 3 4 5 1
1 2 3 4 5
8
7 4 5 6 1 8 3 2
5 3 6 4 7 5 8 4

Output
1
5
2



-----Note-----

In the first test case, $p^1 = p = [1, 3, 4, 2]$ and the sequence starting from $1$: $1, p[1] = 1, \dots$ is an infinite path.

In the second test case, $p^5 = [1, 2, 3, 4, 5]$ and it obviously contains several infinite paths.

In the third test case, $p^2 = [3, 6, 1, 8, 7, 2, 5, 4]$ and the sequence starting from $4$: $4, p^2[4]=8, p^2[8]=4, \dots$ is an infinite path since $c_4 = c_8 = 4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Krishnakant is standing at $(0,0)$ in the Cartesian plane. He wants to go to the point $(x,y)$ in the same plane using only horizontal and vertical moves of $1$ unit. There are many ways of doing this, and he is writing down all such ways. Each way comprises of few ${H}$ moves and few $V}$ moves. i.e. moves in horizontal and vertical direction respectively. For example, if Krishnakant wants to go to point $(2,2)$ from point $(0,0)$, ${HVHV}$ is one of the possible ways.   

Given the value of ${K}$, he wants to know lexicographically $K^{{th}}$ smallest way of going to $(x,y)$ from $(0,0)$.   

Input Format 

The first line contains an integer ${T}$ , i.e., number of test cases. 

Next ${T}$ lines will contain integers ${x}$,$y$ and ${K}$.  

Output Format 

For each test case, print lexicographically $K^{{th}}$ smallest path.  

Constraints 

$1\leq T\leq1000000$ 

$1\leq x\leq10$ 

$1\leq y\leq10$ 

$0\leq K<\text{number of paths}$ 

Sample Input  

2
2 2 2
2 2 3

Sample Output  

HVVH
VHHV

Explanation

All the paths of going to $(2,2)$ from $(0,0)$ in lexicographically increasing order:

$0.HHVV$

$1.HVHV$

$2.HVVH$

$3.VHHV$

$4.VHVH$

$5.VVHH$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Roma has become the happy owner of a new game World of Darkraft. This game combines elements of virtually all known genres, and on one of the later stages of the game Roma faced difficulties solving a puzzle.

In this part Roma fights with a cunning enemy magician. The battle takes place on a rectangular field plaid n × m. Each cell contains one magical character: L, R or X. Initially all the squares of the field are "active".

The players, Roma and enemy magician, take turns. Roma makes the first move. During a move a player selects one of the active cells. Then depending on the image in the character in the cell one of the following actions takes place: 

  * L — magical waves radiate from the cell to the left downwards and to the right upwards along diagonal paths. All cells on the path of the waves (including the selected cell too) become inactive. The waves continue until the next inactive cell or to the edge of the field if there are no inactive cells on the way. 
  * R — the magical waves radiate to the left upwards and to the right downwards. 
  * X — the magical waves radiate in all four diagonal directions. 



If the next player cannot make a move (i.e., all cells are inactive), he loses.

Roma has been trying to defeat the computer opponent for three days but he just keeps losing. He asks you to help him and determine whether it is guaranteed that he can beat the opponent, or he will have to hack the game.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 20).

Next n lines contain m characters describing the playing field: the j-th character of the i-th line equals to the magical character of the corresponding field square.

Output

On the first line print "WIN" if Roma can win or "LOSE" if it is impossible to win considering that the opponent pays optimally.

Examples

Input

2 2
RL
LR


Output

LOSE


Input

2 2
RR
RR


Output

WIN

Note

In the first test each move makes one diagonal line of the square inactive, thus it is guaranteed that Roma loses after two moves.

There are three variants of making a move in the second test: to "finish off" the main diagonal line or any of the squares that are left. That means that after three moves the game stops and Roma wins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Santa Claus and Candies

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Santa Claus has *n* candies, he dreams to give them as gifts to children.

What is the maximal number of children for whose he can give candies if Santa Claus want each kid should get distinct positive integer number of candies. Santa Class wants to give all *n* candies he has.

Input Specification:
The only line contains positive integer number *n* (1<=≤<=*n*<=≤<=1000) — number of candies Santa Claus has.

Output Specification:
Print to the first line integer number *k* — maximal number of kids which can get candies.

Print to the second line *k* distinct integer numbers: number of candies for each of *k* kid. The sum of *k* printed numbers should be exactly *n*.

If there are many solutions, print any of them.

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

Demo Output:
['2\n2 3\n', '3\n3 5 1\n', '1\n2 \n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Jeff's friends know full well that the boy likes to get sequences and arrays for his birthday. Thus, Jeff got sequence *p*1,<=*p*2,<=...,<=*p**n* for his birthday.

Jeff hates inversions in sequences. An inversion in sequence *a*1,<=*a*2,<=...,<=*a**n* is a pair of indexes *i*,<=*j* (1<=≤<=*i*<=&lt;<=*j*<=≤<=*n*), such that an inequality *a**i*<=&gt;<=*a**j* holds.

Jeff can multiply some numbers of the sequence *p* by -1. At that, he wants the number of inversions in the sequence to be minimum. Help Jeff and find the minimum number of inversions he manages to get.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=2000). The next line contains *n* integers — sequence *p*1, *p*2, ..., *p**n* (|*p**i*|<=≤<=105). The numbers are separated by spaces.

Output Specification:
In a single line print the answer to the problem — the minimum number of inversions Jeff can get.

Demo Input:
['2\n2 1\n', '9\n-2 0 -1 0 -1 2 1 0 -1\n']

Demo Output:
['0\n', '6\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a binary string S. Alice and Bob are playing a game on it.

Each turn, the following happens:

1. Alice selects a 01 subsequence in S and removes it from S. (a 01 subsequence is a length 2 subsequence whose first character is 0 and second character is 1)
2. Bob selects a 01 subsequence in S and removes it from S.
3. After both players have moved, the turn is called completed and Alice scores 1 point. Then, the next turn begins.

If either player is unable to move (there isn't any 01 subsequence left in S), that turn ends immediately and the game ends.

Alice tries to maximize her points, while Bob tries to minimize Alice's points. Find how many points Alice would score if both players play optimally.

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

- The first line contains a single integer T — the number of test cases. 
- Each of the next T lines contains a binary string S.

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

For each test case, output on a new line a single integer — Alice's score when both players play optimally.

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

$1 ≤ T ≤ 2\cdot 10^{5}$
- The sum of $|S|$ across all tests doesn't exceed  $2 \cdot 10^{5}$

------ subtasks ------ 

Subtask 1 (25 Points):
The sum of $|S|$ across all tests doesn't exceed $100$
Subtask 2 (25 Points):
The sum of $|S|$ across all tests doesn't exceed $1500$
Subtask 3 (50 Points):
No further constraints.

----- Sample Input 1 ------ 
4
01010101
0101
10
01001011

----- Sample Output 1 ------ 
1 
1 
0 
2 

----- explanation 1 ------ 
In the first example, this is one of the possible outcomes.

Turn $1$:
- Alice removes subsequence $(1, 2)$ from $S$, so $S$ becomes 010101.
- Bob removes subsequence $(3, 6)$ from $S$, so $S$ becomes 0110.
- Alice scores one point and the first turn ends.

Turn 2:
- Alice removes subsequence $(1, 2)$ from $S$, so $S$ becomes 10.
- Bob has nothing to do, so the game ends immediately.

Thus, Alice has one point in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Fox And Names

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Fox Ciel is going to publish a paper on FOCS (Foxes Operated Computer Systems, pronounce: "Fox"). She heard a rumor: the authors list on the paper is always sorted in the lexicographical order. 

After checking some examples, she found out that sometimes it wasn't true. On some papers authors' names weren't sorted in lexicographical order in normal sense. But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!

She wants to know, if there exists an order of letters in Latin alphabet such that the names on the paper she is submitting are following in the lexicographical order. If so, you should find out any such order.

Lexicographical order is defined in following way. When we compare *s* and *t*, first we find the leftmost position with differing characters: *s**i*<=≠<=*t**i*. If there is no such position (i. e. *s* is a prefix of *t* or vice versa) the shortest string is less. Otherwise, we compare characters *s**i* and *t**i* according to their order in alphabet.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=100): number of names.

Each of the following *n* lines contain one string *name**i* (1<=≤<=|*name**i*|<=≤<=100), the *i*-th name. Each name contains only lowercase Latin letters. All names are different.

Output Specification:
If there exists such order of letters that the given names are sorted lexicographically, output any such order as a permutation of characters 'a'–'z' (i. e. first output the first letter of the modified alphabet, then the second, and so on).

Otherwise output a single word "Impossible" (without quotes).

Demo Input:
['3\nrivest\nshamir\nadleman\n', '10\ntourist\npetr\nwjmzbmr\nyeputons\nvepifanov\nscottwu\noooooooooooooooo\nsubscriber\nrowdark\ntankengineer\n', '10\npetr\negor\nendagorion\nfeferivan\nilovetanyaromanova\nkostka\ndmitriyh\nmaratsnowbear\nbredorjaguarturnik\ncgyforever\n', '7\ncar\ncare\ncareful\ncarefully\nbecarefuldontforgetsomething\notherwiseyouwillbehacked\ngoodluck\n']

Demo Output:
['bcdefghijklmnopqrsatuvwxyz\n', 'Impossible\n', 'aghjlnopefikdmbcqrstuvwxyz\n', 'acbdefhijklmnogpqrstuvwxyz\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
As you could know there are no male planes nor female planes. However, each plane on Earth likes some other plane. There are *n* planes on Earth, numbered from 1 to *n*, and the plane with number *i* likes the plane with number *f**i*, where 1<=≤<=*f**i*<=≤<=*n* and *f**i*<=≠<=*i*.

We call a love triangle a situation in which plane *A* likes plane *B*, plane *B* likes plane *C* and plane *C* likes plane *A*. Find out if there is any love triangle on Earth.

Input Specification:
The first line contains a single integer *n* (2<=≤<=*n*<=≤<=5000) — the number of planes.

The second line contains *n* integers *f*1,<=*f*2,<=...,<=*f**n* (1<=≤<=*f**i*<=≤<=*n*, *f**i*<=≠<=*i*), meaning that the *i*-th plane likes the *f**i*-th.

Output Specification:
Output «YES» if there is a love triangle consisting of planes on Earth. Otherwise, output «NO».

You can output any letter in lower case or in upper case.

Demo Input:
['5\n2 4 5 1 3\n', '5\n5 5 5 5 1\n']

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

Note:
In first example plane 2 likes plane 4, plane 4 likes plane 1, plane 1 likes plane 2 and that is a love triangle.

In second example there are no love triangles.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every day we can send from the server a certain limit of e-mails.

Task:
Write a function that will return the integer number of e-mails sent in the percentage of the limit.

Example:
```
limit       - 1000;
emails sent - 101;
return      - 10%; // becouse integer from 10,1 = 10
```

Arguments:

Integer, limit;
Integer, number of e-mails sent today;

When:

the argument ```$sent = 0```, then return the message: "No e-mails sent";
the argument ```$sent >= $limit```, then return the message: "Daily limit is reached";
the argument ```$limit is empty```, then default ```$limit = 1000``` emails;

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the first step to understanding FizzBuzz.  

Your inputs:
a positive integer, n, greater than or equal to one.
n is provided, you have NO CONTROL over its value.

Your expected output is an array of positive integers from 1 to n (inclusive).

Your job is to write an algorithm that gets you from the input to the output.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valera has 2·*n* cubes, each cube contains an integer from 10 to 99. He arbitrarily chooses *n* cubes and puts them in the first heap. The remaining cubes form the second heap. 

Valera decided to play with cubes. During the game he takes a cube from the first heap and writes down the number it has. Then he takes a cube from the second heap and write out its two digits near two digits he had written (to the right of them). In the end he obtained a single fourdigit integer — the first two digits of it is written on the cube from the first heap, and the second two digits of it is written on the second cube from the second heap.

Valera knows arithmetic very well. So, he can easily count the number of distinct fourdigit numbers he can get in the game. The other question is: how to split cubes into two heaps so that this number (the number of distinct fourdigit integers Valera can get) will be as large as possible?

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=100). The second line contains 2·*n* space-separated integers *a**i* (10<=≤<=*a**i*<=≤<=99), denoting the numbers on the cubes.

Output Specification:
In the first line print a single number — the maximum possible number of distinct four-digit numbers Valera can obtain. In the second line print 2·*n* numbers *b**i* (1<=≤<=*b**i*<=≤<=2). The numbers mean: the *i*-th cube belongs to the *b**i*-th heap in your division.

If there are multiple optimal ways to split the cubes into the heaps, print any of them.

Demo Input:
['1\n10 99\n', '2\n13 24 13 45\n']

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

Note:
In the first test case Valera can put the first cube in the first heap, and second cube — in second heap. In this case he obtain number 1099. If he put the second cube in the first heap, and the first cube in the second heap, then he can obtain number 9910. In both cases the maximum number of distinct integers is equal to one.

In the second test case Valera can obtain numbers 1313, 1345, 2413, 2445. Note, that if he put the first and the third cubes in the first heap, he can obtain only two numbers 1324 and 1345.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Bob has a rectangular chocolate bar of the size *W*<=×<=*H*. He introduced a cartesian coordinate system so that the point (0,<=0) corresponds to the lower-left corner of the bar, and the point (*W*,<=*H*) corresponds to the upper-right corner. Bob decided to split the bar into pieces by breaking it. Each break is a segment parallel to one of the coordinate axes, which connects the edges of the bar. More formally, each break goes along the line *x*<==<=*x**c* or *y*<==<=*y**c*, where *x**c* and *y**c* are integers. It should divide one part of the bar into two non-empty parts. After Bob breaks some part into two parts, he breaks the resulting parts separately and independently from each other. Also he doesn't move the parts of the bar. Bob made *n* breaks and wrote them down in his notebook in arbitrary order. At the end he got *n*<=+<=1 parts. Now he wants to calculate their areas. Bob is lazy, so he asks you to do this task.

Input Specification:
The first line contains 3 integers *W*, *H* and *n* (1<=≤<=*W*,<=*H*,<=*n*<=≤<=100) — width of the bar, height of the bar and amount of breaks. Each of the following *n* lines contains four integers *x**i*,<=1,<=*y**i*,<=1,<=*x**i*,<=2,<=*y**i*,<=2 — coordinates of the endpoints of the *i*-th break (0<=≤<=*x**i*,<=1<=≤<=*x**i*,<=2<=≤<=*W*,<=0<=≤<=*y**i*,<=1<=≤<=*y**i*,<=2<=≤<=*H*, or *x**i*,<=1<==<=*x**i*,<=2, or *y**i*,<=1<==<=*y**i*,<=2). Breaks are given in arbitrary order.

It is guaranteed that the set of breaks is correct, i.e. there is some order of the given breaks that each next break divides exactly one part of the bar into two non-empty parts.

Output Specification:
Output *n*<=+<=1 numbers — areas of the resulting parts in the increasing order.

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

Demo Output:
['1 1 2 ', '1 1 1 1 ', '2 2 4 ']

Note:
none

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