vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Polycarp is writing the prototype of a graphic editor. He has already made up his mind that the basic image transformations in his editor will be: rotate the image 90 degrees clockwise, flip the image horizontally (symmetry relative to the vertical line, that is, the right part of the image moves to the left, and vice versa) and zooming on the image. He is sure that that there is a large number of transformations that can be expressed through these three.

He has recently stopped implementing all three transformations for monochrome images. To test this feature, he asked you to write a code that will consecutively perform three actions with a monochrome image: first it will rotate the image 90 degrees clockwise, then it will flip the image horizontally and finally, it will zoom in twice on the image (that is, it will double all the linear sizes).

Implement this feature to help Polycarp test his editor.


-----Input-----

The first line contains two integers, w and h (1 ≤ w, h ≤ 100) — the width and height of an image in pixels. The picture is given in h lines, each line contains w characters — each character encodes the color of the corresponding pixel of the image. The line consists only of characters "." and "*", as the image is monochrome.


-----Output-----

Print 2w lines, each containing 2h characters — the result of consecutive implementing of the three transformations, described above.


-----Examples-----
Input
3 2
.*.
.*.

Output
....
....
****
****
....
....

Input
9 20
**.......
****.....
******...
*******..
..******.
....****.
......***
*.....***
*********
*********
*********
*********
....**...
...****..
..******.
.********
****..***
***...***
**.....**
*.......*

Output
********......**********........********
********......**********........********
********........********......********..
********........********......********..
..********......********....********....
..********......********....********....
..********......********..********......
..********......********..********......
....********....****************........
....********....****************........
....********....****************........
....********....****************........
......******************..**********....
......******************..**********....
........****************....**********..
........****************....**********..
............************......**********
............************......**********

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two villages are separated by a river that flows from the north to the south. The villagers want to build a bridge across the river to make it easier to move across the villages.

The river banks can be assumed to be vertical straight lines x = a and x = b (0 < a < b).

The west village lies in a steppe at point O = (0, 0). There are n pathways leading from the village to the river, they end at points A_{i} = (a, y_{i}). The villagers there are plain and simple, so their pathways are straight segments as well.

The east village has reserved and cunning people. Their village is in the forest on the east bank of the river, but its exact position is not clear. There are m twisted paths leading from this village to the river and ending at points B_{i} = (b, y'_{i}). The lengths of all these paths are known, the length of the path that leads from the eastern village to point B_{i}, equals l_{i}.

The villagers want to choose exactly one point on the left bank of river A_{i}, exactly one point on the right bank B_{j} and connect them by a straight-line bridge so as to make the total distance between the villages (the sum of |OA_{i}| + |A_{i}B_{j}| + l_{j}, where |XY| is the Euclidean distance between points X and Y) were minimum. The Euclidean distance between points (x_1, y_1) and (x_2, y_2) equals $\sqrt{(x_{1} - x_{2})^{2} +(y_{1} - y_{2})^{2}}$.

Help them and find the required pair of points.


-----Input-----

The first line contains integers n, m, a, b (1 ≤ n, m ≤ 10^5, 0 < a < b < 10^6). 

The second line contains n integers in the ascending order: the i-th integer determines the coordinate of point A_{i} and equals y_{i} (|y_{i}| ≤ 10^6). 

The third line contains m integers in the ascending order: the i-th integer determines the coordinate of point B_{i} and equals y'_{i} (|y'_{i}| ≤ 10^6). 

The fourth line contains m more integers: the i-th of them determines the length of the path that connects the eastern village and point B_{i}, and equals l_{i} (1 ≤ l_{i} ≤ 10^6).

It is guaranteed, that there is such a point C with abscissa at least b, that |B_{i}C| ≤ l_{i} for all i (1 ≤ i ≤ m). It is guaranteed that no two points A_{i} coincide. It is guaranteed that no two points B_{i} coincide.


-----Output-----

Print two integers — the numbers of points on the left (west) and right (east) banks, respectively, between which you need to build a bridge. You can assume that the points on the west bank are numbered from 1 to n, in the order in which they are given in the input. Similarly, the points on the east bank are numbered from 1 to m in the order in which they are given in the input.

If there are multiple solutions, print any of them. The solution will be accepted if the final length of the path will differ from the answer of the jury by no more than 10^{ - 6} in absolute or relative value.


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

Output
2 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is learning linear algebra. Recently, he learnt that for a square matrix $M$, $\mathop{\rm trace}(M)$ is defined as the sum of all elements on the main diagonal of $M$ (an element lies on the main diagonal if its row index and column index are equal).
Now, Chef wants to solve some excercises related to this new quantity, so he wrote down a square matrix $A$ with size $N\times N$. A square submatrix of $A$ with size $l\times l$ is a contiguous block of $l\times l$ elements of $A$. Formally, if $B$ is a submatrix of $A$ with size $l\times l$, then there must be integers $r$ and $c$ ($1\le r, c \le N+1-l$) such that $B_{i,j} = A_{r+i-1, c+j-1}$ for each $1 \le i, j \le l$.
Help Chef find the maximum trace of a square submatrix of $A$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$-th of these lines contains $N$ space-separated integers $A_{i,1}, A_{i,2}, \dots, A_{i, N}$ denoting the $i$-th row of the matrix $A$.

-----Output-----
For each test case, print a single line containing one integer — the maximum possible trace.

-----Constraints-----
- $1 \le T \le 100$
- $2 \le N \le 100$
- $1 \le A_{i,j} \le 100$ for each valid $i, j$

-----Subtasks-----
Subtask #1 (100 points): original constraints

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

-----Example Output-----
13

-----Explanation-----
Example case 1: The submatrix with the largest trace is 
6 3
2 7

which has trace equal to $6 + 7 = 13$. (This submatrix is obtained for $r=2, c=1, l=2$.)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is multi-talented. He has developed a cure for coronavirus called COVAC-19. Now that everyone in the world is infected, it is time to distribute it throughout the world efficiently to wipe out coronavirus from the Earth. Chef just cooks the cure, you are his distribution manager.
In the world, there are $N$ countries (numbered $1$ through $N$) with populations $a_1, a_2, \ldots, a_N$. Each cure can be used to cure one infected person once. Due to lockdown rules, you may only deliver cures to one country per day, but you may choose that country arbitrarily and independently on each day. Days are numbered by positive integers. On day $1$, Chef has $x$ cures ready. On each subsequent day, Chef can supply twice the number of cures that were delivered (i.e. people that were cured) on the previous day. Chef cannot supply leftovers from the previous or any earlier day, as the cures expire in a day. The number of cures delivered to some country on some day cannot exceed the number of infected people it currently has, either.
However, coronavirus is not giving up so easily. It can infect a cured person that comes in contact with an infected person again ― formally, it means that the number of infected people in a country doubles at the end of each day, i.e. after the cures for this day are used (obviously up to the population of that country).
Find the minimum number of days needed to make the world corona-free.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $x$.
- The second line contains $N$ space-separated integers $a_1, a_2, \ldots, a_N$.

-----Output-----
For each test case, print a single line containing one integer ― the minimum number of days.

-----Constraints-----
- $1 \le T \le 10^3$
- $1 \le N \le 10^5$
- $1 \le a_i \le 10^9$ for each valid $i$
- $1 \le x \le 10^9$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (20 points): $a_1 = a_2 = \ldots = a_N$
Subtask #2 (80 points): original constraints

-----Example Input-----
3
5 5
1 2 3 4 5
5 1
40 30 20 10 50
3 10
20 1 110

-----Example Output-----
5
9
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Description
Blithchron is the annual cultural festival of IIT Gandhinagar. A popular event in Blithchron is Adrenaline - a treasure hunt. At a particular stage in Adrenaline, the contestants will come to a vault, whose combination can be deciphered only using the previous clue. The previous clue contains one small word W, and a large (meaningless) string of characters S. The combination to open the vault (N) is the number of times W appears in S such that the characters of the W are in the same order. There may be other characters of S interspersed
between them.

Design a program that can crack the combination of the vault.

Input Format
First line contains W
Second line contains the meaningless sequence S

Output Format
One line containing the number of times W appears in S

SAMPLE INPUT
COW
CCOOWW

SAMPLE OUTPUT
8

Explanation

W =  COW appears once in S = CWOW, twice in S = CCOW, and eight times in S = CCOOWW

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are initially X people in a room. 

You are given an array A of length N which describes the following events:
If A_{i} ≥ 0, then A_{i} people enter the room at i-th minute. For e.g. if A_{2} = 3, then 3 people enter the room at the 2-nd minute.
If A_{i} < 0, then |A_{i}| people leave the room at i-th minute. Here |A_{i}| denotes the absolute value of A_{i}. For e.g. if A_{4} = -2, then 2 people leave the room at the 4-th minute.

Determine the maximum number of people in the room at any moment of time.

It is guaranteed in the input that at any moment of time, the number of people in the room does not become negative.

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

- The first line will contain T - the number of test cases. Then the test cases follow.
- The first line of each test case consists of two integers N and X - the length of the array A and the number of people in the room initially.
- The second line of each test case contains N integers A_{1}, A_{2}, A_{3}, \dots A_{N}.

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

For each testcase, output the maximum number of people in the room at any point of time.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$0 ≤ X ≤ 100$
$-100 ≤ A_{i} ≤ 100$

----- Sample Input 1 ------ 
3
5 8
0 3 3 -13 5
4 5
0 -2 2 3
3 5
-2 5 -2

----- Sample Output 1 ------ 
14
8
8

----- explanation 1 ------ 
Test case-1: In the $3$-rd minute, the room contains $8 + 0 + 3 + 3 = 14$ people which is the maximum number of people in the room at any point of time.

Test case-2: In the $4$-th minute, the room contains $5 + 0 - 2 + 2 + 3 = 8$ people which is the maximum number of people in the room at any point of time.

Test case-3: In the $2$-nd minute, the room contains $5 - 2 + 5 = 8$ people which is the maximum number of people in the room at any point of time.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Galileo's latest project involves determining the density of stars in certain regions of the sky. For this purpose he started looking for datasets online, and discovered a dataset on Newton's blog. Newton had decomposed the night sky into a Voronoi tessellation with the generators arranged in a grid. He has stored the number of stars in a Voronoi cell at a position in a matrix that corresponds to the position of the generator in the grid.
This dataset does not directly help Galileo, because he needs to be able to query the number of stars in a rectangular portion of the sky. Galileo tried to write a program that does this on his own, but it turned out to be too slow. Can you help him?

-----Input Format-----
The first line contains two integers n and m that denote the height and width of the matrix respectively. This is followed by  n lines each containing m integers each.
The line following this would contain a single integer t, the number of queries to be run. Each query line consists of 4 integers px, py, qx, qy. The first two integers denote the row and column numbers of the upper left corner of the rectangular region, and the second pair of numbers correspond to the lower right corner.

-----Output Format-----
For each query output a single line containing the number of stars in that rectangular region.

-----Example-----
Input:

3 3
10 10 10
10 10 10
10 10 10
4
1 1 1 1
1 1 3 3
2 1 3 3
3 1 3 3

Output:

10
90
60
30

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Goo is working in a well-known Slovak antivirus company which unfortunately cannot be named. In addition to antivirus software, they are developing a spam filter. Recently, Goo has made a few improvements to the filter and he wants to demonstrate his progress to his boss. As you can imagine, demonstrating low-level ideas of your implementation is not a good way to impress your boss, so Goo instead decided to make a presentation with plenty of graphs showing filtering results. The company has a huge database of e-mails and each e-mail is marked as a spam or ham (i.e. not spam). These e-mails were all correctly marked by people – every time someone in the company receives an e-mail, he marks it as either spam or ham and adds it to the database.

The success of Goo’s program can be measured in a simple way. Goo ran his program on all e-mails in the database. For each message he noted if his program correctly decided whether the message was spam or ham. The messages were processed in order from the oldest to the newest one. To impress the boss, Goo wants to select e-mails from a period of time and calculate the success rate only for this period. Of course, a period containing only one e-mail won’t impress anyone, so Goo wants to choose a period which is long enough.

-----Task-----
You are given a sequence of test results and a number $k$. Your task is to find a continuous subsequence of length at least $k$ which has the highest possible success rate among all such subsequences. The success rate of a subsequence is defined as the number of successfully classified e-mails divided by the length of the subsequence.

-----Input description-----
On the first line there is an integer $k$ ($1\le k \le 100$) denoting the minimal subsequence length. The second line contains a string consisting of characters 0 and 1, denoting answers of the program for each e-mail in the database. Number 1 indicates that Goo’s program gave a correct answer and 0 that it failed. The length of the string will be at least $k$ and at most $100000$ characters.

-----Output description-----
The first and only line of output should consist of two integers $f$ and $\ell $, separated by a single space. The integer $f$ is the 1-based index of the first element of subsequence with the best success rate and $\ell $ is its length. If there are multiple optimal solutions, you can output any one of them.

-----Examples-----
Sample Input:
1
01
Sample Output:
2 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let N be a positive odd number.

There are N coins, numbered 1, 2, \ldots, N. For each i (1 \leq i \leq N), when Coin i is tossed, it comes up heads with probability p_i and tails with probability 1 - p_i.

Taro has tossed all the N coins. Find the probability of having more heads than tails.

Constraints

* N is an odd number.
* 1 \leq N \leq 2999
* p_i is a real number and has two decimal places.
* 0 < p_i < 1

Input

Input is given from Standard Input in the following format:


N
p_1 p_2 \ldots p_N


Output

Print the probability of having more heads than tails. The output is considered correct when the absolute error is not greater than 10^{-9}.

Examples

Input

3
0.30 0.60 0.80


Output

0.612


Input

1
0.50


Output

0.5


Input

5
0.42 0.01 0.42 0.99 0.42


Output

0.3821815872

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The king's birthday dinner was attended by $k$ guests. The dinner was quite a success: every person has eaten several dishes (though the number of dishes was the same for every person) and every dish was served alongside with a new set of kitchen utensils.

All types of utensils in the kingdom are numbered from $1$ to $100$. It is known that every set of utensils is the same and consist of different types of utensils, although every particular type may appear in the set at most once. For example, a valid set of utensils can be composed of one fork, one spoon and one knife.

After the dinner was over and the guests were dismissed, the king wondered what minimum possible number of utensils could be stolen. Unfortunately, the king has forgotten how many dishes have been served for every guest but he knows the list of all the utensils left after the dinner. Your task is to find the minimum possible number of stolen utensils.


-----Input-----

The first line contains two integer numbers $n$ and $k$ ($1 \le n \le 100, 1 \le k \le 100$)  — the number of kitchen utensils remaining after the dinner and the number of guests correspondingly.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 100$)  — the types of the utensils remaining. Equal values stand for identical utensils while different values stand for different utensils.


-----Output-----

Output a single value — the minimum number of utensils that could be stolen by the guests.


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

Output
1

Input
10 3
1 3 3 1 3 5 5 5 5 100

Output
14



-----Note-----

In the first example it is clear that at least one utensil of type $3$ has been stolen, since there are two guests and only one such utensil. But it is also possible that every person received only one dish and there were only six utensils in total, when every person got a set $(1, 2, 3)$ of utensils. Therefore, the answer is $1$.

One can show that in the second example at least $2$ dishes should have been served for every guest, so the number of utensils should be at least $24$: every set contains $4$ utensils and every one of the $3$ guests gets two such sets. Therefore, at least $14$ objects have been stolen. Please note that utensils of some types (for example, of types $2$ and $4$ in this example) may be not present in the set served for dishes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
E: Do You Divide It? / Do you want to chop it up?

story

Mr. T has been terribly troubled by the problem of plane figures in programming contests he has participated in in the past, and has had a strong grudge against plane figures ever since.

Above all, I have mixed feelings about polygons drawn on a two-dimensional plane, so when I see a polygon, I can't help but chop it up.

When Mr. T chops a polygon, he covers the polygon with a plate with slits at intervals of 0.5 width parallel to the y-axis, and chops and discards the invisible part with the slits.

However, Mr. T does not like unilateral killing, so in order to leave the buds of recurrence in the polygon, care should be taken to make the total area of ​​the figures remaining after chopping as large as possible.

Let's find the area of ​​the figure that remains after Mr. T chops it.

problem

The two-dimensional plane has an infinite length slit in the y-axis direction, and the visible part and the invisible part are switched every 0.5 in the x-axis direction.

As shown in the figure below, a polygon consisting of N vertices continues to translate in the positive x-axis direction on this plane.

<image>

Output the area of ​​the visible part at the moment when the visible part of the polygon becomes the largest.

Input format

Give N in the first line. In the i-th line of the following N lines, the i-th vertex coordinates (x_i, y_i) in the counterclockwise direction of the polygon are given.

The following can be assumed.

* All inputs are integers
* 3 ≤ N ≤ 100, −10 ^ 3 ≤ x_i, y_i ≤ 10 ^ 3
* Given polygons do not share edges or vertices with anything other than adjacent line segments.
* The three consecutive vertices of a given polygon are not on the same straight line



Output format

Output the visible area in one line at the moment when the visible part of the given polygon becomes the largest. Absolute error and relative error are allowed up to 10 ^ {-5}.

Input example 1


6
0 0
-1 -2
3 -2
2 0
3 2
-1 2


Output example 1


6.000000000

Input example 2


Five
0 0
twenty two
4 -2
4 2
twenty two


Output example 2


6.50000000





Example

Input

6
0 0
-1 -2
3 -2
2 0
3 2
-1 2


Output

6.000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this kata you must take an input string, reverse the order of the words, and reverse the order of the letters within the words.

But, as a bonus, every test input will end with a punctuation mark (! ? .) and the output should be returned with the mark at the end.

A few examples should help clarify:

```python
esrever("hello world.") == "dlrow olleh."

esrever("Much l33t?") == "t33l hcuM?"

esrever("tacocat!") == "tacocat!"
```

Quick Note: A string will always be passed in (though it may be empty) so no need for error-checking other types.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a tree with N vertices, numbered 1, 2, \ldots, N. For each i (1 \leq i \leq N - 1), the i-th edge connects Vertex x_i and y_i.

Taro has decided to paint each vertex in white or black, so that any black vertex can be reached from any other black vertex by passing through only black vertices.

You are given a positive integer M. For each v (1 \leq v \leq N), answer the following question:

* Assuming that Vertex v has to be black, find the number of ways in which the vertices can be painted, modulo M.

Constraints

* All values in input are integers.
* 1 \leq N \leq 10^5
* 2 \leq M \leq 10^9
* 1 \leq x_i, y_i \leq N
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N M
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}


Output

Print N lines. The v-th (1 \leq v \leq N) line should contain the answer to the following question:

* Assuming that Vertex v has to be black, find the number of ways in which the vertices can be painted, modulo M.

Examples

Input

3 100
1 2
2 3


Output

3
4
3


Input

4 100
1 2
1 3
1 4


Output

8
5
5
5


Input

1 100


Output

1


Input

10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7


Output

0
0
1
1
1
0
1
0
1
1

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