vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Little Petya often visits his grandmother in the countryside. The grandmother has a large vertical garden, which can be represented as a set of `n` rectangles of varying height. Due to the newest irrigation system we can create artificial rain above them.

Creating artificial rain is an expensive operation. That's why we limit ourselves to creating the artificial rain only above one section. The water will then flow to the neighbouring sections but only if each of their heights does not exceed the height of the previous watered section.

___

## Example:

Let's say there's a garden consisting of 5 rectangular sections of heights `4, 2, 3, 3, 2`.

Creating the artificial rain over the left-most section is inefficient as the water **WILL FLOW DOWN** to the section with the height of `2`, but it **WILL NOT FLOW UP** to the section with the height of `3` from there. Only 2 sections will be covered: `4, 2`.

The most optimal choice will be either of the sections with the height of `3` because the water will flow to its neighbours covering 4 sections altogether: `2, 3, 3, 2`. You can see this process in the following illustration:



___

As Petya is keen on programming, he decided to find such section that if we create artificial rain above it, the number of watered sections will be maximal.

## Output:
The maximal number of watered sections if we create artificial rain above exactly one section.

**Note: performance will be tested.**

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Chef is given an array of numbers and asked to find the first balance point of an array. A balance point is an index in the array N where the sum of the integers to the left of N is equal to the sum of the integers to the right of N. If there is no such balance point, print -1

-----Input-----
The first line of the input contains an 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 denoting the number of weights on the array. The second line contains N space-separated integers A1, A2, ..., AN denoting the weights

-----Output-----
For each test case, output a single line containing the index of the first balance point. If no such index exists, output -1

-----Constraints-----
For Subtask 1:
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 10
- -1000 ≤ A1, A2, ..., AN ≤ 1000
For Subtask 1:
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 1000
- -10000 ≤ A1, A2, ..., AN ≤ 10000

-----Example-----
Input:
2
7
7 8 9 1 9 8 7
6
1 100 50 -51 1 1

Output:
3
1

-----Explanation-----
Example case 1. In the first case, at the midpoint of the array 1, the sum of the left side {7,8,9} is equal to the sum of the right side {9,8,7}
Example case 1. In the second case, at index 1, the sum of left side =1 is equal to the sum of the right side {50,-51,1,1}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"Intelligence is a very result of hard work, behind every drop of intelligence there is a ocean of hard work" - Unknown

So our guy Ankur likes a girl G very much. But as we all know G likes only intelligent guys. 
So if Ankur has to impress her then he has to show his intelligence. But G too is an intelligent girl, so he came up with a task for Ankur.
The task is -
Ankur has to collect flowers for her and put them into baskets, but flowers are scattered all around,
 each flower has a position say (x,y). Each basket can hold only two flowers, but putting flowers into basket has a special cost. 
 If two flowers at positions (x1,y1) and (x2,y2) are being put into a basket then cost of putting them will be 
 the euclidean distance between them ( sqrt(square(x2-x1) + square((y2-y1))).

So there are 2*N flowers and N baskets. 
He has to put all the flowers into the baskets and give her the final total cost.
But this total cost would be minimum.
Hence He has to minimize Summation ( c1+c2+c3+...+cn) , where ci is the cost of putting two flowers into ith basket.
ci = sqrt(square(x2-x1) + square((y2-y1)) , if two flowers at coordinates (x1,y1) and (x2,y2) are being put into ith basket

Input

First line gives the number of testcases  1 ≤ T ≤ 100.
Each case starts with an integer N (1 ≤ N ≤ 8). The next 2*N lines will give
the coordinates of a flower. Each line starts with the x coordinate and then the y coordinate. Both x, y are integers in the range 0 to 1000. 

Output

For each case, output the minimum total cost, rounded to 2 decimal places. Follow the sample for exact format.

SAMPLE INPUT
3
1
9 9
10 10
2
0 0
1 0
4 1
5 1
5
10 10
20 10
5 5
1 1
120 3
6 6
50 60
3 24
6 9
0 0

SAMPLE OUTPUT
1.41
2.00
118.40

Explanation

For the first case we can just put both the flowers in the basket, so the cost will be sqrt((10-9)(10-9)+(10-9)(10-9))
For the second case we can put flower(0,0) and flower(1,0) in first basket, so c1 = sqrt((1-0)(1-0)+(0-0)(0-0)) and c2 = sqrt((5-4)(5-4)+(1-1)(1-1))
this (c1+c2) would be minimum.
but if we put let's say (0,0) and (4,1) in first and (1,0) and (5,1) in second, the (c1+c2) would not be minimum.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef had an array A with length N, but some of its elements got lost. Now, each element of this array is either unknown (denoted by -1) or a positive integer not exceeding K.
Chef decided to restore the array A by replacing each unknown element by a positive integer not exceeding K.
However, Chef has M restrictions that must hold for the restored array. There are two types of restrictions:

- I L R, meaning that for each i such that L < i ≤ R, the condition Ai - Ai-1 = 1 should be satisfied.
- D L R, meaning that for each i such that L < i  ≤ R, the condition Ai - Ai-1 = -1 should be satisfied.

Chef would like to know the number of ways to restore the array while satisfying all restrictions, modulo 109+7.

-----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 three space-separated integers N, M and K.
- The second line contains N integers A1, A2, ..., AN.
- Each of the following M lines contains one restriction in the form I L R or D L R.

-----Output-----
For each test case, print a single line containing one integer - the number of ways to restore the array modulo 109+7.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N, M ≤ 100,000
- 1 ≤ K ≤ 1,000,000,000
- 1 ≤ L < R ≤ N
- 1 ≤ Ai ≤ K or Ai = -1 for each valid i
- 1 ≤ sum of N over all test cases ≤ 500,000
- 1 ≤ sum of M over all test cases ≤ 500,000

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

3
4 2 10
2 3 5 4
I 1 2 
D 3 4
5 2 10
-1 -1 -1 -1 -1
I 1 3
D 3 5
6 2 2
-1 -1 -1 -1 -1 -1
I 1 4
D 4 6

Output:

1
8
0

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Iahub got lost in a very big desert. The desert can be represented as a *n*<=×<=*n* square matrix, where each cell is a zone of the desert. The cell (*i*,<=*j*) represents the cell at row *i* and column *j* (1<=≤<=*i*,<=*j*<=≤<=*n*). Iahub can go from one cell (*i*,<=*j*) only down or right, that is to cells (*i*<=+<=1,<=*j*) or (*i*,<=*j*<=+<=1). 

Also, there are *m* cells that are occupied by volcanoes, which Iahub cannot enter. 

Iahub is initially at cell (1,<=1) and he needs to travel to cell (*n*,<=*n*). Knowing that Iahub needs 1 second to travel from one cell to another, find the minimum time in which he can arrive in cell (*n*,<=*n*).

Input Specification:
The first line contains two integers *n* (1<=≤<=*n*<=≤<=109) and *m* (1<=≤<=*m*<=≤<=105). Each of the next *m* lines contains a pair of integers, *x* and *y* (1<=≤<=*x*,<=*y*<=≤<=*n*), representing the coordinates of the volcanoes.

Consider matrix rows are numbered from 1 to *n* from top to bottom, and matrix columns are numbered from 1 to *n* from left to right. There is no volcano in cell (1,<=1). No two volcanoes occupy the same location.

Output Specification:
Print one integer, the minimum time in which Iahub can arrive at cell (*n*,<=*n*). If no solution exists (there is no path to the final cell), print -1.

Demo Input:
['4 2\n1 3\n1 4\n', '7 8\n1 6\n2 6\n3 5\n3 6\n4 3\n5 1\n5 2\n5 3\n', '2 2\n1 2\n2 1\n']

Demo Output:
['6\n', '12\n', '-1\n']

Note:
Consider the first sample. A possible road is: (1, 1)  →  (1, 2)  →  (2, 2)  →  (2, 3)  →  (3, 3)  →  (3, 4)  →  (4, 4).

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got another geometrical task. You are given two non-degenerate polygons *A* and *B* as vertex coordinates. Polygon *A* is strictly convex. Polygon *B* is an arbitrary polygon without any self-intersections and self-touches. The vertices of both polygons are given in the clockwise order. For each polygon no three consecutively following vertices are located on the same straight line.

Your task is to check whether polygon *B* is positioned strictly inside polygon *A*. It means that any point of polygon *B* should be strictly inside polygon *A*. "Strictly" means that the vertex of polygon *B* cannot lie on the side of the polygon *A*.

Input Specification:
The first line contains the only integer *n* (3<=≤<=*n*<=≤<=105) — the number of vertices of polygon *A*. Then *n* lines contain pairs of integers *x**i*,<=*y**i* (|*x**i*|,<=|*y**i*|<=≤<=109) — coordinates of the *i*-th vertex of polygon *A*. The vertices are given in the clockwise order.

The next line contains a single integer *m* (3<=≤<=*m*<=≤<=2·104) — the number of vertices of polygon *B*. Then following *m* lines contain pairs of integers *x**j*,<=*y**j* (|*x**j*|,<=|*y**j*|<=≤<=109) — the coordinates of the *j*-th vertex of polygon *B*. The vertices are given in the clockwise order.

The coordinates of the polygon's vertices are separated by a single space. It is guaranteed that polygons *A* and *B* are non-degenerate, that polygon *A* is strictly convex, that polygon *B* has no self-intersections and self-touches and also for each polygon no three consecutively following vertices are located on the same straight line.

Output Specification:
Print on the only line the answer to the problem — if polygon *B* is strictly inside polygon *A*, print "YES", otherwise print "NO" (without the quotes).

Demo Input:
['6\n-2 1\n0 3\n3 3\n4 1\n3 -2\n2 -2\n4\n0 1\n2 2\n3 1\n1 0\n', '5\n1 2\n4 2\n3 -3\n-2 -2\n-2 1\n4\n0 1\n1 2\n4 1\n2 -1\n', '5\n-1 2\n2 3\n4 1\n3 -2\n0 -3\n5\n1 0\n1 1\n3 1\n5 -1\n2 -1\n']

Demo Output:
['YES\n', 'NO\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 a binary string $s$.

Find the number of distinct cyclical binary strings of length $n$ which contain $s$ as a substring.

The cyclical string $t$ contains $s$ as a substring if there is some cyclical shift of string $t$, such that $s$ is a substring of this cyclical shift of $t$.

For example, the cyclical string "000111" contains substrings "001", "01110" and "10", but doesn't contain "0110" and "10110".

Two cyclical strings are called different if they differ from each other as strings. For example, two different strings, which differ from each other by a cyclical shift, are still considered different cyclical strings.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 40$) — the length of the target string $t$.

The next line contains the string $s$ ($1 \le |s| \le n$) — the string which must be a substring of cyclical string $t$. String $s$ contains only characters '0' and '1'.


-----Output-----

Print the only integer — the number of distinct cyclical binary strings $t$, which contain $s$ as a substring.


-----Examples-----
Input
2
0

Output
3
Input
4
1010

Output
2
Input
20
10101010101010

Output
962


-----Note-----

In the first example, there are three cyclical strings, which contain "0" — "00", "01" and "10".

In the second example, there are only two such strings — "1010", "0101".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Завтра у хоккейной команды, которой руководит Евгений, важный матч. Евгению нужно выбрать шесть игроков, которые выйдут на лед в стартовом составе: один вратарь, два защитника и три нападающих.

Так как это стартовый состав, Евгения больше волнует, насколько красива будет команда на льду, чем способности игроков. А именно, Евгений хочет выбрать такой стартовый состав, чтобы номера любых двух игроков из стартового состава отличались не более, чем в два раза. Например, игроки с номерами 13, 14, 10, 18, 15 и 20 устроят Евгения, а если, например, на лед выйдут игроки с номерами 8 и 17, то это не устроит Евгения.

Про каждого из игроков вам известно, на какой позиции он играет (вратарь, защитник или нападающий), а также его номер. В хоккее номера игроков не обязательно идут подряд. Посчитайте число различных стартовых составов из одного вратаря, двух защитников и трех нападающих, которые может выбрать Евгений, чтобы выполнялось его условие красоты.


-----Входные данные-----

Первая строка содержит три целых числа g, d и f (1 ≤ g ≤ 1 000, 1 ≤ d ≤ 1 000, 1 ≤ f ≤ 1 000) — число вратарей, защитников и нападающих в команде Евгения. 

Вторая строка содержит g целых чисел, каждое в пределах от 1 до 100 000 — номера вратарей.

Третья строка содержит d целых чисел, каждое в пределах от 1 до 100 000 — номера защитников.

Четвертая строка содержит f целых чисел, каждое в пределах от 1 до 100 000 — номера нападающих.

Гарантируется, что общее количество игроков не превосходит 1 000, т. е. g + d + f ≤ 1 000. Все g + d + f номеров игроков различны.


-----Выходные данные-----

Выведите одно целое число — количество возможных стартовых составов.


-----Примеры-----
Входные данные
1 2 3
15
10 19
20 11 13

Выходные данные
1

Входные данные
2 3 4
16 40
20 12 19
13 21 11 10

Выходные данные
6



-----Примечание-----

В первом примере всего один вариант для выбора состава, который удовлетворяет описанным условиям, поэтому ответ 1.

Во втором примере подходят следующие игровые сочетания (в порядке вратарь-защитник-защитник-нападающий-нападающий-нападающий):  16 20 12 13 21 11  16 20 12 13 11 10  16 20 19 13 21 11  16 20 19 13 11 10  16 12 19 13 21 11  16 12 19 13 11 10 

Таким образом, ответ на этот пример — 6.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've decided to carry out a survey in the theory of prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors.

Consider positive integers *a*, *a*<=+<=1, ..., *b* (*a*<=≤<=*b*). You want to find the minimum integer *l* (1<=≤<=*l*<=≤<=*b*<=-<=*a*<=+<=1) such that for any integer *x* (*a*<=≤<=*x*<=≤<=*b*<=-<=*l*<=+<=1) among *l* integers *x*, *x*<=+<=1, ..., *x*<=+<=*l*<=-<=1 there are at least *k* prime numbers. 

Find and print the required minimum *l*. If no value *l* meets the described limitations, print -1.

Input Specification:
A single line contains three space-separated integers *a*,<=*b*,<=*k* (1<=≤<=*a*,<=*b*,<=*k*<=≤<=106; *a*<=≤<=*b*).

Output Specification:
In a single line print a single integer — the required minimum *l*. If there's no solution, print -1.

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

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

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In this task Anna and Maria play a game with a very unpleasant rival. Anna and Maria are in the opposite squares of a chessboard (8<=×<=8): Anna is in the upper right corner, and Maria is in the lower left one. Apart from them, the board has several statues. Each statue occupies exactly one square. A square that contains a statue cannot have anything or anyone — neither any other statues, nor Anna, nor Maria.

Anna is present on the board as a figurant (she stands still and never moves), and Maria has been actively involved in the game. Her goal is — to come to Anna's square. Maria and statues move in turn, Maria moves first. During one move Maria can go to any adjacent on the side or diagonal cell in which there is no statue, or she can stay in the cell where she is. The statues during their move must go one square down simultaneously, and those statues that were in the bottom row fall from the board and are no longer appeared.

At that moment, when one of the statues is in the cell in which the Maria is, the statues are declared winners. At the moment when Maria comes into the cell where Anna has been waiting, Maria is declared the winner.

Obviously, nothing depends on the statues, so it all depends on Maria. Determine who will win, if Maria does not make a strategic error.

Input Specification:
You are given the 8 strings whose length equals 8, describing the initial position on the board. The first line represents the top row of the board, the next one — for the second from the top, and so on, the last line represents the bottom row. Each character string matches a single cell board in the appropriate row, and the characters are in the same manner as that of the corresponding cell. If the cell is empty, the corresponding character is ".". If a cell has Maria, then it is represented by character "M". If a cell has Anna, it is represented by the character "A". If a cell has a statue, then the cell is represented by character "S".

It is guaranteed that the last character of the first row is always "A", the first character of the last line is always "M". The remaining characters are "." or "S".

Output Specification:
If Maria wins, print string "WIN". If the statues win, print string "LOSE".

Demo Input:
['.......A\n........\n........\n........\n........\n........\n........\nM.......\n', '.......A\n........\n........\n........\n........\n........\nSS......\nM.......\n', '.......A\n........\n........\n........\n........\n.S......\nS.......\nMS......\n']

Demo Output:
['WIN\n', 'LOSE\n', 'LOSE\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Elephant loves magic squares very much.

A magic square is a 3 × 3 table, each cell contains some positive integer. At that the sums of integers in all rows, columns and diagonals of the table are equal. The figure below shows the magic square, the sum of integers in all its rows, columns and diagonals equals 15. $\left. \begin{array}{|c|c|c|} \hline 4 & {9} & {2} \\ \hline 3 & {5} & {7} \\ \hline 8 & {1} & {6} \\ \hline \end{array} \right.$ 

The Little Elephant remembered one magic square. He started writing this square on a piece of paper, but as he wrote, he forgot all three elements of the main diagonal of the magic square. Fortunately, the Little Elephant clearly remembered that all elements of the magic square did not exceed 10^5. 

Help the Little Elephant, restore the original magic square, given the Elephant's notes.


-----Input-----

The first three lines of the input contain the Little Elephant's notes. The first line contains elements of the first row of the magic square. The second line contains the elements of the second row, the third line is for the third row. The main diagonal elements that have been forgotten by the Elephant are represented by zeroes.

It is guaranteed that the notes contain exactly three zeroes and they are all located on the main diagonal. It is guaranteed that all positive numbers in the table do not exceed 10^5.


-----Output-----

Print three lines, in each line print three integers — the Little Elephant's magic square. If there are multiple magic squares, you are allowed to print any of them. Note that all numbers you print must be positive and not exceed 10^5.

It is guaranteed that there exists at least one magic square that meets the conditions.


-----Examples-----
Input
0 1 1
1 0 1
1 1 0

Output
1 1 1
1 1 1
1 1 1

Input
0 3 6
5 0 5
4 7 0

Output
6 3 6
5 5 5
4 7 4

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

The kindergarten attached to the University of Aizu is a kindergarten where children who love programming gather. Yu, one of the kindergarten children, loves darts as much as programming. Yu-kun was addicted to darts recently, but he got tired of ordinary darts, so he decided to make his own darts board.

See darts for darts.

Problem

The contents of the darts that Yu-kun thought about are as follows.

The infinitely wide darts board has several polygons with scores. The player has only one darts arrow. The player throws an arrow and stabs the arrow into one of the polygons to get the score written there. If you stab it in any other way, you will not get any points.

Yu-kun decided where to throw the arrow, but it doesn't always stick exactly. The darts board is a two-dimensional plane, and the position Yu-kun is aiming for is a point (cx, cy). The place where the arrow thrown by Yu-kun sticks is selected with a uniform probability from any point included in the circle with radius r centered on the point (cx, cy). The coordinates of the exposed points do not have to be integers.

Since the information on the darts board, the position (cx, cy) that Yu-kun aims at, and the radius r are given, answer the expected value of the score that Yu-kun can get.

Constraints

The input satisfies the following conditions.

* All inputs are given as integers
* 1 ≤ n ≤ 50
* 0 ≤ cx, cy, x, y ≤ 1000
* 1 ≤ r ≤ 100
* 3 ≤ p ≤ 10
* 1 ≤ score ≤ 100
* Polygon vertices are given in such an order that they visit adjacent vertices clockwise or counterclockwise.
* The sides of a polygon do not have anything in common with the sides of another polygon
* A polygon does not contain another polygon
* If the arrow sticks on the side of the polygon, no score will be given.

Input


n cx cy r
Information on the 0th polygon
Information on the first polygon
...
Information on the (n-1) th polygon


n is the number of polygons on the darts board. Polygonal information is given in the following format.


p score
x0 y0
x1 y1
...
x (p-1) y (p-1)


p represents the number of vertices of the polygon, and score represents the score written on the polygon. Each line segment of the polygon is a line segment connecting the vertices of (xi, yi) and (xi + 1, yi + 1) (i <p-1), and (xp-1, yp-1) and (x0, It is a line segment connecting the vertices of y0).

Output

Output the expected value of the score that Yu-kun can get in one line. Any number of digits after the decimal point may be output. However, the error in the answer must not exceed 0.000001 (10-6).

Examples

Input

1 2 2 1
4 1
0 0
2 0
2 2
0 2


Output

0.2500000000


Input

1 2 2 1
4 1
0 0
5 0
5 5
0 5


Output

1.0000000000


Input

4 3 3 2
3 1
1 1
3 3
1 5
4 2
2 0
5 0
4 2
3 2
3 3
4 3
6 1
6 5
4 4
3 4
4 4
5 6
2 6


Output

1.0574955319


Input

1 10 10 1
4 10
0 0
1 0
1 1
0 1


Output

0.0000000000

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