vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given are N points on the circumference of a circle centered at (0,0) in an xy-plane. The coordinates of the i-th point are (\cos(\frac{2\pi T_i}{L}),\sin(\frac{2\pi T_i}{L})).

Three distinct points will be chosen uniformly at random from these N points. Find the expected x- and y-coordinates of the center of the circle inscribed in the triangle formed by the chosen points.

Constraints

* 3 \leq N \leq 3000
* N \leq L \leq 10^9
* 0 \leq T_i \leq L-1
* T_i<T_{i+1}
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N L
T_1
:
T_N


Output

Print the expected x- and y-coordinates of the center of the circle inscribed in the triangle formed by the chosen points. Your output will be considered correct when the absolute or relative error is at most 10^{-9}.

Examples

Input

3 4
0
1
3


Output

0.414213562373095 -0.000000000000000


Input

4 8
1
3
5
6


Output

-0.229401949926902 -0.153281482438188


Input

10 100
2
11
35
42
54
69
89
91
93
99


Output

0.352886583546338 -0.109065017701873

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Apple, a gourmet, works as editor-in-chief of a gastronomic periodical. He travels around the world, tasting new delights of famous chefs from the most fashionable restaurants. Mr. Apple has his own signature method of review  — in each restaurant Mr. Apple orders two sets of dishes on two different days. All the dishes are different, because Mr. Apple doesn't like to eat the same food. For each pair of dishes from different days he remembers exactly which was better, or that they were of the same quality. After this the gourmet evaluates each dish with a positive integer.

Once, during a revision of a restaurant of Celtic medieval cuisine named «Poisson», that serves chestnut soup with fir, warm soda bread, spicy lemon pie and other folk food, Mr. Apple was very pleasantly surprised the gourmet with its variety of menu, and hence ordered too much. Now he's confused about evaluating dishes.

The gourmet tasted a set of $n$ dishes on the first day and a set of $m$ dishes on the second day. He made a table $a$ of size $n \times m$, in which he described his impressions. If, according to the expert, dish $i$ from the first set was better than dish $j$ from the second set, then $a_{ij}$ is equal to ">", in the opposite case $a_{ij}$ is equal to "<". Dishes also may be equally good, in this case $a_{ij}$ is "=".

Now Mr. Apple wants you to help him to evaluate every dish. Since Mr. Apple is very strict, he will evaluate the dishes so that the maximal number used is as small as possible. But Mr. Apple also is very fair, so he never evaluates the dishes so that it goes against his feelings. In other words, if $a_{ij}$ is "<", then the number assigned to dish $i$ from the first set should be less than the number of dish $j$ from the second set, if $a_{ij}$ is ">", then it should be greater, and finally if $a_{ij}$ is "=", then the numbers should be the same.

Help Mr. Apple to evaluate each dish from both sets so that it is consistent with his feelings, or determine that this is impossible.


-----Input-----

The first line contains integers $n$ and $m$ ($1 \leq n, m \leq 1000$) — the number of dishes in both days.

Each of the next $n$ lines contains a string of $m$ symbols. The $j$-th symbol on $i$-th line is $a_{ij}$. All strings consist only of "<", ">" and "=".


-----Output-----

The first line of output should contain "Yes", if it's possible to do a correct evaluation for all the dishes, or "No" otherwise.

If case an answer exist, on the second line print $n$ integers — evaluations of dishes from the first set, and on the third line print $m$ integers — evaluations of dishes from the second set.


-----Examples-----
Input
3 4
>>>>
>>>>
>>>>

Output
Yes
2 2 2 
1 1 1 1 

Input
3 3
>>>
<<<
>>>

Output
Yes
3 1 3 
2 2 2 

Input
3 2
==
=<
==

Output
No



-----Note-----

In the first sample, all dishes of the first day are better than dishes of the second day. So, the highest score will be $2$, for all dishes of the first day.

In the third sample, the table is contradictory — there is no possible evaluation of the dishes that satisfies it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shil likes Round numbers very much . A  number is called Round number if its non-negative and its first and last digits are same. For example  0 , 3 , 343 and  50005 are round numbers whereas 1000 is not  a round number. Shil has  an array A1 , A2  .. AN . He wants to answer Q queries of following two type :
1 l r  : Find total number of round numbers in range [l, r]
2 i K  : Update i^th element of array A to K  i.e perform the  operation Ai = K. 
Since you are the friend of Shil , he asks for your help .

INPUT:
First line consists of two integers N and Q. Next line consists of N integers A1 , A2  .. AN. Next line consists of Q queries. Each query consists of three integers as mentioned in the problem.

OUTPUT: 
For each query of type 2 , output total number of round numbers in range [l,r].

CONSTRAINTS:
1 ≤ N , Q ≤ 2*10^5
-10^18 ≤ Ai ≤ 10^18 
1 ≤ l,r ≤ N
-10^18 ≤ K ≤ 10^18

SAMPLE INPUT
5 5 
1 2 33 456 111
1 1 2
1 1 5
2 1 6
2 2 1000
1 1 5

SAMPLE OUTPUT
2
4
3

Explanation

Out of all the initial numbers given in array A :- 1,2,33,111 are round numbers .
For 1^st query , there are two round numbers - A[1] and A[2].
For 2^st query , there are 4 round numbers - A[1] , A[2] , A[3] , A[5].
In   3^rd query , we are updating 1st position with 6 , which is a round number.
In   4^th query , we are updating 2nd position with 1000 , which isn't a round number.  
For 5^th query , there are 3 round numbers - A[1] , A[3] and  A[5].

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya has sequence *a* consisting of *n* integers.

The subsequence of the sequence *a* is such subsequence that can be obtained from *a* by removing zero or more of its elements.

Two sequences are considered different if index sets of numbers included in them are different. That is, the values ​of the elements ​do not matter in the comparison of subsequences. In particular, any sequence of length *n* has exactly 2*n* different subsequences (including an empty subsequence).

A subsequence is considered lucky if it has a length exactly *k* and does not contain two identical lucky numbers (unlucky numbers can be repeated any number of times).

Help Petya find the number of different lucky subsequences of the sequence *a*. As Petya's parents don't let him play with large numbers, you should print the result modulo prime number 1000000007 (109<=+<=7).

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=105). The next line contains *n* integers *a**i* (1<=≤<=*a**i*<=≤<=109) — the sequence *a*.

Output Specification:
On the single line print the single number — the answer to the problem modulo prime number 1000000007 (109<=+<=7).

Demo Input:
['3 2\n10 10 10\n', '4 2\n4 4 7 7\n']

Demo Output:
['3\n', '4\n']

Note:
In the first sample all 3 subsequences of the needed length are considered lucky.

In the second sample there are 4 lucky subsequences. For them the sets of indexes equal (the indexation starts from 1): {1, 3}, {1, 4}, {2, 3} and {2, 4}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp loves ciphers. He has invented his own cipher called repeating.

Repeating cipher is used for strings. To encrypt the string s=s_{1}s_{2} ... s_{m} (1 ≤ m ≤ 10), Polycarp uses the following algorithm:

  * he writes down s_1 ones, 
  * he writes down s_2 twice, 
  * he writes down s_3 three times, 
  * ... 
  * he writes down s_m m times. 



For example, if s="bab" the process is: "b" → "baa" → "baabbb". So the encrypted s="bab" is "baabbb".

Given string t — the result of encryption of some string s. Your task is to decrypt it, i. e. find the string s.

Input

The first line contains integer n (1 ≤ n ≤ 55) — the length of the encrypted string. The second line of the input contains t — the result of encryption of some string s. It contains only lowercase Latin letters. The length of t is exactly n.

It is guaranteed that the answer to the test exists.

Output

Print such string s that after encryption it equals t.

Examples

Input


6
baabbb


Output


bab

Input


10
ooopppssss


Output


oops

Input


1
z


Output


z

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Apart from having lots of holidays throughout the year, residents of Berland also have whole lucky years. Year is considered lucky if it has no more than 1 non-zero digit in its number. So years 100, 40000, 5 are lucky and 12, 3001 and 12345 are not.

You are given current year in Berland. Your task is to find how long will residents of Berland wait till the next lucky year.


-----Input-----

The first line contains integer number n (1 ≤ n ≤ 10^9) — current year in Berland.


-----Output-----

Output amount of years from the current year to the next lucky one.


-----Examples-----
Input
4

Output
1

Input
201

Output
99

Input
4000

Output
1000



-----Note-----

In the first example next lucky year is 5. In the second one — 300. In the third — 5000.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Not so long ago, Vlad came up with an interesting function:

$f_a(x)=\left\lfloor\frac{x}{a}\right\rfloor + x mod a$, where $\left\lfloor\frac{x}{a}\right\rfloor$ is $\frac{x}{a}$, rounded down, $x mod a$ — the remainder of the integer division of $x$ by $a$.

For example, with $a=3$ and $x=11$, the value $f_3(11) = \left\lfloor\frac{11}{3}\right\rfloor + 11 mod 3 = 3 + 2 = 5$.

The number $a$ is fixed and known to Vlad. Help Vlad find the maximum value of $f_a(x)$ if $x$ can take any integer value from $l$ to $r$ inclusive ($l \le x \le r$).


-----Input-----

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

This is followed by $t$ lines, each of which contains three integers $l_i$, $r_i$ and $a_i$ ($1 \le l_i \le r_i \le 10^9, 1 \le a_i \le 10^9$) — the left and right boundaries of the segment and the fixed value of $a$.


-----Output-----

For each test case, output one number on a separate line — the maximum value of the function on a given segment for a given $a$.


-----Examples-----

Input
5
1 4 3
5 8 4
6 10 6
1 1000000000 1000000000
10 12 8
Output
2
4
5
999999999
5


-----Note-----

In the first sample:

$f_3(1) = \left\lfloor\frac{1}{3}\right\rfloor + 1 mod 3 = 0 + 1 = 1$,

$f_3(2) = \left\lfloor\frac{2}{3}\right\rfloor + 2 mod 3 = 0 + 2 = 2$,

$f_3(3) = \left\lfloor\frac{3}{3}\right\rfloor + 3 mod 3 = 1 + 0 = 1$,

$f_3(4) = \left\lfloor\frac{4}{3}\right\rfloor + 4 mod 3 = 1 + 1 = 2$

As an answer, obviously, $f_3(2)$ and $f_3(4)$ are suitable.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"Ring Ring!!"  
Sherlock's phone suddenly started ringing. And it was none other than Jim Moriarty..
"Long time no see ! You miss me right ? Anyway we'll talk about it later . Let me first tell you something. Dr.Watson is with me . And you've got only one chance to save him . Here's your challenge:.
Given a number N and another number M, tell if the remainder of N%M is odd or even. If it's odd, then print "ODD" else print "EVEN" 

If Sherlock can answer the query correctly, then Watson will be set free. He has approached you for help since you being a programmer.Can you help him? 

-----Input-----
The first line contains, T, the number of test cases..
Each test case contains an integer, N and M

-----Output-----
Output the minimum value for each test case 

-----Constraints-----
1 = T = 20
1 <= N <= 10^18 
1 <= M<= 10^9 

-----Subtasks-----
Subtask #1 : (20 points)
1 = T = 20
1 <= N <= 100 
1 <= M<= 100 

Subtask 2 : (80 points) 

1 = T = 20
1 <= N <= 10^18 
1 <= M<= 10^9 

-----Example-----
Input:
2
4 4
6 5

Output:
EVEN
ODD

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Peter has lined up hay bales. Some hay bales contain parasites and he wants to move the infected hay bales to the back of the sequence, to minimize the chance that the parasites spread. To sort the haybales, he repeatedly takes out any three consecutive hay bales and puts them back in sorted order. Your task is to calculate the minimum number of operations Peter has to execute to sort the sequence.

-----Input-----
The input contains a single string $s$ ($3 \leq |s| \leq 500$), the sequence of hay bales. Each character of $s$ is either ‘C’ (for a clean hay bale) or ‘P’ (for an infected one).

-----Output-----
The output must contain one integer, the minimum number of steps Peter has to execute.

-----Examples-----
Sample Input 1:
CPCC
Sample Output 1:
1

Sample Input 2:
PPPPCCCC
Sample Output 2:
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
## Task
 You are given an array of integers. On each move you are allowed to increase exactly one of its element by one. Find the minimal number of moves required to obtain a strictly increasing sequence from the input.

## Example

 For `arr = [1, 1, 1]`, the output should be `3`.

## Input/Output


 - `[input]` integer array `arr`

    Constraints:

    `3 ≤ inputArray.length ≤ 100,`

    `-10000 ≤ inputArray[i] ≤ 10000.`
    

 - `[output]` an integer

    The minimal number of moves needed to obtain a strictly increasing sequence from inputArray.

    It's guaranteed that for the given test cases the answer always fits signed 32-bit integer type.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of size N containing level order traversal of a BST. The task is to complete the function constructBst(), that construct the BST (Binary Search Tree) from its given level order traversal.
Example 1:
Input:
N = 9
BST[] = {7,4,12,3,6,8,1,5,10}
Output: 7 4 3 1 6 5 12 8 10
Explanation: After constructing BST, the
preorder traversal of BST is
7 4 3 1 6 5 12 8 10.
Example 2:
Input:
N = 6
BST[] = {1,3,4,6,7,8}
Output: 1 3 4 6 7 8
Explanation: After constructing BST, the
preorder traversal of BST is 1 3 4 6 7 8.
Your Task:
Your task is to complete the function constructBst() which has two arguments, first as the array containing level order traversal of BST and next argument as the length of array which return the root of the newly constructed BST. The preorder traversal of the tree is printed by the driver's code.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Flamel is making the Elixir of Life but he is missing a secret ingredient, a set of contiguous plants (substring) from the Garden of Eden.
The garden consists of various plants represented by string S, where each letter represents a different plant.  But the prophecy has predicted that the correct set of plants required to make the potion will appear in the same contiguous pattern (substring) at the beginning of the forest (prefix), the end of the forest (suffix), and will also be the most frequent sequence present in the entire forest.
Identify the substring of plants required to make the elixir and find out the number of times it appears in the forest. 
Example 1:
Input: S = "ababaaaab"
Output: 3
Explanation: Substring "ab" is a prefix, 
It is also a suffix and appears 3 times.
Example 2:
Input: S = "aaaa"
Output: 4
Explanation: Substring "aaaa" occurs 1 time, 
Substring "aaa" occurs 2 times, substring 
"aa" occurs 3 times, substring "a" occurs 
4 times. All of them are proper prefixes 
and suffixes. But, "a" has the maximum 
frequency.
Example 3:
Input: S = "abcdef"
Output: 1
Your Task: 
You don't need to read input or print anything. Complete the function maxFrequency() which takes string S as input parameter and returns the frequency of the most frequent substring of S which is also a prefix and suffix of the original string.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints: 
1 ≤ |S| ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Notice that the memory limit is non-standard.

Recently Arthur and Sasha have studied correct bracket sequences. Arthur understood this topic perfectly and become so amazed about correct bracket sequences, so he even got himself a favorite correct bracket sequence of length 2n. Unlike Arthur, Sasha understood the topic very badly, and broke Arthur's favorite correct bracket sequence just to spite him.

All Arthur remembers about his favorite sequence is for each opening parenthesis ('(') the approximate distance to the corresponding closing one (')'). For the i-th opening bracket he remembers the segment [l_{i}, r_{i}], containing the distance to the corresponding closing bracket.

Formally speaking, for the i-th opening bracket (in order from left to right) we know that the difference of its position and the position of the corresponding closing bracket belongs to the segment [l_{i}, r_{i}].

Help Arthur restore his favorite correct bracket sequence!


-----Input-----

The first line contains integer n (1 ≤ n ≤ 600), the number of opening brackets in Arthur's favorite correct bracket sequence. 

Next n lines contain numbers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} < 2n), representing the segment where lies the distance from the i-th opening bracket and the corresponding closing one. 

The descriptions of the segments are given in the order in which the opening brackets occur in Arthur's favorite sequence if we list them from left to right.


-----Output-----

If it is possible to restore the correct bracket sequence by the given data, print any possible choice.

If Arthur got something wrong, and there are no sequences corresponding to the given information, print a single line "IMPOSSIBLE" (without the quotes).


-----Examples-----
Input
4
1 1
1 1
1 1
1 1

Output
()()()()

Input
3
5 5
3 3
1 1

Output
((()))

Input
3
5 5
3 3
2 2

Output
IMPOSSIBLE

Input
3
2 3
1 4
1 4

Output
(())()

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob is a theoretical coder - he doesn't write code, but comes up with theories, formulas and algorithm ideas. You are his secretary, and he has tasked you with writing the code for his newest project - a method for making the short form of a word. Write a function ```shortForm```(C# ```ShortForm```, Python ```short_form```) that takes a string and returns it converted into short form using the rule: Remove all vowels, except for those that are the first or last letter. Do not count 'y' as a vowel, and ignore case. Also note, the string given will not have any spaces; only one word, and only Roman letters. 

Example:
```
shortForm("assault");
short_form("assault")
ShortForm("assault");
// should return "asslt"
```

 
Also, FYI: I got all the words with no vowels from 
https://en.wikipedia.org/wiki/English_words_without_vowels

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A jail has a number of prisoners and a number of treats to pass out to them.  Their jailer decides the fairest way to divide the treats is to seat the prisoners around a circular table in sequentially numbered chairs.  A chair number will be drawn from a hat.  Beginning with the prisoner in that chair, one candy will be handed to each prisoner sequentially around the table until all have been distributed.

The jailer is playing a little joke, though.  The last piece of candy looks like all the others, but it tastes awful.  Determine the chair number occupied by the prisoner who will receive that candy.

Example  

$n=4$ 

$m=6$ 

$s=2$  

There are $4$ prisoners, $6$ pieces of candy and distribution starts at chair $2$.  The prisoners arrange themselves in seats numbered $1$ to $4$.  Prisoners receive candy at positions $2,3,4,1,2,3$.  The prisoner to be warned sits in chair number $3$.  

Function Description

Complete the saveThePrisoner function in the editor below.  It should return an integer representing the chair number of the prisoner to warn.  

saveThePrisoner has the following parameter(s):  

int n:  the number of prisoners  
int m:  the number of sweets  
int s:  the chair number to begin passing out sweets from  

Returns  

int: the chair number of the prisoner to warn

Input Format

The first line contains an integer, $\boldsymbol{\boldsymbol{t}}$, the number of test cases. 

The next $\boldsymbol{\boldsymbol{t}}$ lines each contain $3$ space-separated integers: 

$n$: the number of prisoners  
$m$: the number of sweets  
$s$: the chair number to start passing out treats at  

Constraints

$1\leq t\leq100$  
$1\leq n\leq10^9$
$1\leq m\leq10^9$
$1\leq s\leq n$

Sample Input 0
2
5 2 1
5 2 2

Sample Output 0
2
3

Explanation 0

In the first query, there are $n=5$ prisoners and $m=2$ sweets. Distribution starts at seat number $s=1$.  Prisoners in seats numbered $1$ and $2$ get sweets.  Warn prisoner $2$.   

In the second query, distribution starts at seat $2$ so prisoners in seats $2$ and $3$ get sweets.  Warn prisoner $3$.

Sample Input 1
2
7 19 2
3 7 3

Sample Output 1
6
3

Explanation 1

In the first test case, there are $n=7$ prisoners, $m=19$ sweets and they are passed out starting at chair $s=2$.  The candies go all around twice and there are $5$ more candies passed to each prisoner from seat $2$ to seat $\boldsymbol{6}$.  

In the second test case, there are $n=3$ prisoners, $m=7$ candies and they are passed out starting at seat $s=3$.  They go around twice, and there is one more to pass out to the prisoner at seat $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Instead of one grid various square grids of odd length came into existence later after the old grid was recovered. Now researchers came to know that for such grids the sum of all the numbers except the middle element is equal to the middle element of the grid. Now since all numbers are disappeared so you need to find total possible solutions the grid can possess. Remember that each element of the grid solution should possess only non negative numbers 
Input
First line contains t (test cases) ,next t lines contain N and M as input  , N will be odd and is the size of the grid and M is the value of the middle element of the grid 
Output
You have to output count of total solutions that the grid can posses mod 10^9+7.
Scoring
1≤ t,N,M ≤ 10      20pts
1≤ t,N,M ≤ 100    30pts
1≤ t ≤ 10^5 , 1≤ N,M ≤ 10^3  50pts

SAMPLE INPUT
1
3 1

SAMPLE OUTPUT
8

Explanation

The all possible solutions to the grid are insert 1 in 8 distinct positions and fill rest with zeros.

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