vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Weather Tomorrow

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya came up with his own weather forecasting method. He knows the information about the average air temperature for each of the last *n* days. Assume that the average air temperature for each day is integral.

Vasya believes that if the average temperatures over the last *n* days form an arithmetic progression, where the first term equals to the average temperature on the first day, the second term equals to the average temperature on the second day and so on, then the average temperature of the next (*n*<=+<=1)-th day will be equal to the next term of the arithmetic progression. Otherwise, according to Vasya's method, the temperature of the (*n*<=+<=1)-th day will be equal to the temperature of the *n*-th day.

Your task is to help Vasya predict the average temperature for tomorrow, i. e. for the (*n*<=+<=1)-th day.

Input Specification:
The first line contains a single integer *n* (2<=≤<=*n*<=≤<=100) — the number of days for which the average air temperature is known.

The second line contains a sequence of integers *t*1,<=*t*2,<=...,<=*t**n* (<=-<=1000<=≤<=*t**i*<=≤<=1000) — where *t**i* is the average temperature in the *i*-th day.

Output Specification:
Print the average air temperature in the (*n*<=+<=1)-th day, which Vasya predicts according to his method. Note that the absolute value of the predicted temperature can exceed 1000.

Demo Input:
['5\n10 5 0 -5 -10\n', '4\n1 1 1 1\n', '3\n5 1 -5\n', '2\n900 1000\n']

Demo Output:
['-15\n', '1\n', '-5\n', '1100\n']

Note:
In the first example the sequence of the average temperatures is an arithmetic progression where the first term is 10 and each following terms decreases by 5. So the predicted average temperature for the sixth day is  - 10 - 5 =  - 15.

In the second example the sequence of the average temperatures is an arithmetic progression where the first term is 1 and each following terms equals to the previous one. So the predicted average temperature in the fifth day is 1.

In the third example the average temperatures do not form an arithmetic progression, so the average temperature of the fourth day equals to the temperature of the third day and equals to  - 5.

In the fourth example the sequence of the average temperatures is an arithmetic progression where the first term is 900 and each the following terms increase by 100. So predicted average temperature in the third day is 1000 + 100 = 1100.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a grid of square cells with H horizontal rows and W vertical columns. The cell at the i-th row and the j-th column will be denoted as Cell (i, j).

In Cell (i, j), a_{ij} coins are placed.

You can perform the following operation any number of times:

Operation: Choose a cell that was not chosen before and contains one or more coins, then move one of those coins to a vertically or horizontally adjacent cell.

Maximize the number of cells containing an even number of coins.

Constraints

* All values in input are integers.
* 1 \leq H, W \leq 500
* 0 \leq a_{ij} \leq 9

Input

Input is given from Standard Input in the following format:


H W
a_{11} a_{12} ... a_{1W}
a_{21} a_{22} ... a_{2W}
:
a_{H1} a_{H2} ... a_{HW}


Output

Print a sequence of operations that maximizes the number of cells containing an even number of coins, in the following format:


N
y_1 x_1 y_1' x_1'
y_2 x_2 y_2' x_2'
:
y_N x_N y_N' x_N'


That is, in the first line, print an integer N between 0 and H \times W (inclusive), representing the number of operations.

In the (i+1)-th line (1 \leq i \leq N), print four integers y_i, x_i, y_i' and x_i' (1 \leq y_i, y_i' \leq H and 1 \leq x_i, x_i' \leq W), representing the i-th operation. These four integers represents the operation of moving one of the coins placed in Cell (y_i, x_i) to a vertically or horizontally adjacent cell, (y_i', x_i').

Note that if the specified operation violates the specification in the problem statement or the output format is invalid, it will result in Wrong Answer.

Examples

Input

2 3
1 2 3
0 1 1


Output

3
2 2 2 3
1 1 1 2
1 3 1 2


Input

3 2
1 0
2 1
1 0


Output

3
1 1 1 2
1 2 2 2
3 1 3 2


Input

1 5
9 9 9 9 9


Output

2
1 1 1 2
1 3 1 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence of integers $A_1,A_2,…,A_N$ and a magical non-zero integer $x$
You have to select a subsegment of sequence A (possibly empty), and replace the elements in that subsegment after dividing them by x.
Formally, replace any one subsegment $A_l, A_{l+1}, ..., A_r$ with $A_l/x, A_{l+1}/x, ..., A_r/x$ where $l \leq r$
What is the minimum possible sum you can obtain?
Note: The given operation can only be performed once

-----Input -----
- The first line of the input contains two positive integer n denoting the size of array, and x
denoting the magical integer
- Next line contains $N$ space separated integers

-----Output-----
Single line containing one real number, denoting the minimum possible sum you can obtain. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-2}$

-----Constraints-----
- $1 \leq n \leq 10^3$
- $1 \leq |x| \leq 10^3$
- $ |A_i| \leq 10^3$

-----Sample Input-----
3 2
1 -2 3

-----Sample Output-----
0.5

-----Explanation-----
Array 1 -2 3, selecting subsegment {3}, you get 1 -2 1.5, which gives $sum=0.5$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every (positive) rational number can be expressed as a ratio of two (positive) integers. However, in decimal form, rational numbers often have an infinitely repeating pattern, e.g., $1/7 = 0.142857142857142857$... A convenient way of writing this repeating pattern is to put a bar over the first occurrence of the repeating part, so $1/7$ would be written:\[ 0.\overline{142857}. \]

Given a rational number consisting of a series of digits, followed by a decimal point, followed by more digits, and then a number indicating how many of the rightmost digits repeat (i.e., the number of digits under the bar), your task is to find the ratio of two integers, in the most reduced form, that represent the same rational number. For example, for the input “$0.142857$ $6$” you should find $1/7$.

-----Input-----
The input will be a single line with two numbers separated by one space. The first number will consist of $1$ to $3$ digits ($0$–$9$), followed by a decimal point, followed by $1$ to $11$ digits ($0$–$9$), representing the decimal form of the number, possibly with leading zeros. The second number will be a positive integer indicating how many of the rightmost digits of the preceding number repeat. The first number will always be greater than $0$. The second number will never be less than $1$ nor larger than the number of digits to the right of the decimal point.

-----Output-----
Print the corresponding fraction in its most reduced form, that is, the fraction with the smallest possible integer values in the numerator and denominator.

-----Examples-----
Sample Input 1:
0.142857 6
Sample Output 1:
1/7

Sample Input 2:
1.6 1
Sample Output 2:
5/3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
You are given a string S.
Your task is to find out whether is a valid regex or not.

=====Input Format=====
The first line contains integer T, the number of test cases.
The next T lines contains the string S.

=====Constraints=====
0<T<100

=====Output Format=====
Print "True" or "False" for each test case without quotes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan on his birthday was presented with array of non-negative integers a_1, a_2, …, a_n. He immediately noted that all a_i satisfy the condition 0 ≤ a_i ≤ 15.

Ivan likes graph theory very much, so he decided to transform his sequence to the graph.

There will be n vertices in his graph, and vertices u and v will present in the graph if and only if binary notations of integers a_u and a_v are differ in exactly one bit (in other words, a_u ⊕ a_v = 2^k for some integer k ≥ 0. Where ⊕ is [Bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)).

A terrible thing happened in a couple of days, Ivan forgot his sequence a, and all that he remembers is constructed graph!

Can you help him, and find any sequence a_1, a_2, …, a_n, such that graph constructed by the same rules that Ivan used will be the same as his graph?

Input

The first line of input contain two integers n,m (1 ≤ n ≤ 500, 0 ≤ m ≤ (n(n-1))/(2)): number of vertices and edges in Ivan's graph.

Next m lines contain the description of edges: i-th line contain two integers u_i, v_i (1 ≤ u_i, v_i ≤ n; u_i ≠ v_i), describing undirected edge connecting vertices u_i and v_i in the graph.

It is guaranteed that there are no multiple edges in the graph. It is guaranteed that there exists some solution for the given graph.

Output

Output n space-separated integers, a_1, a_2, …, a_n (0 ≤ a_i ≤ 15). 

Printed numbers should satisfy the constraints: edge between vertices u and v present in the graph if and only if a_u ⊕ a_v = 2^k for some integer k ≥ 0.

It is guaranteed that there exists some solution for the given graph. If there are multiple possible solutions, you can output any.

Examples

Input


4 4
1 2
2 3
3 4
4 1


Output


0 1 0 1 


Input


3 0


Output


0 0 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N(N+1)/2 dots arranged to form an equilateral triangle whose sides consist of N dots, as shown below. The j-th dot from the left in the i-th row from the top is denoted by (i, j) (1 \leq i \leq N, 1 \leq j \leq i). Also, we will call (i+1, j) immediately lower-left to (i, j), and (i+1, j+1) immediately lower-right to (i, j).

<image>

Takahashi is drawing M polygonal lines L_1, L_2, ..., L_M by connecting these dots. Each L_i starts at (1, 1), and visits the dot that is immediately lower-left or lower-right to the current dots N-1 times. More formally, there exist X_{i,1}, ..., X_{i,N} such that:

* L_i connects the N points (1, X_{i,1}), (2, X_{i,2}), ..., (N, X_{i,N}), in this order.
* For each j=1, 2, ..., N-1, either X_{i,j+1} = X_{i,j} or X_{i,j+1} = X_{i,j}+1 holds.



Takahashi would like to draw these lines so that no part of L_{i+1} is to the left of L_{i}. That is, for each j=1, 2, ..., N, X_{1,j} \leq X_{2,j} \leq ... \leq X_{M,j} must hold.

Additionally, there are K conditions on the shape of the lines that must be followed. The i-th condition is denoted by (A_i, B_i, C_i), which means:

* If C_i=0, L_{A_i} must visit the immediately lower-left dot for the B_i-th move.
* If C_i=1, L_{A_i} must visit the immediately lower-right dot for the B_i-th move.



That is, X_{A_i, {B_i}+1} = X_{A_i, B_i} + C_i must hold.

In how many ways can Takahashi draw M polygonal lines? Find the count modulo 1000000007.

Constraints

* 1 \leq N \leq 20
* 1 \leq M \leq 20
* 0 \leq K \leq (N-1)M
* 1 \leq A_i \leq M
* 1 \leq B_i \leq N-1
* C_i = 0 or 1
* No pair appears more than once as (A_i, B_i).

Input

Input is given from Standard Input in the following format:


N M K
A_1 B_1 C_1
A_2 B_2 C_2
:
A_K B_K C_K


Output

Print the number of ways for Takahashi to draw M polygonal lines, modulo 1000000007.

Examples

Input

3 2 1
1 2 0


Output

6


Input

3 2 2
1 1 1
2 1 0


Output

0


Input

5 4 2
1 3 1
4 2 0


Output

172


Input

20 20 0


Output

881396682

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set of $n$ axis-aligned rectangles in a 2D plane. For this problem, two rectangles are considered to intersect if their boundaries contain any common points (in particular, two nesting rectangles don’t count as intersecting). Determine if some pair of rectangles intersect.

In this example, only rectangles A and B intersect.

-----Input-----
Each test case will begin with a line with a single integer $n$ ($1\! \le \! n\! \le \! 10^5$), which is the number of rectangles.

Each of the next $n$ lines will contain four space-separated integers:$x_1$ $y_1$ $x_2$ $y_2$

($-10^9\! \le \! x_1,y_1,x_2,y_2\! \le \! 10^9, x_1\! <\! x_2, y_1\! <\! y_2$), which describe a rectangle, where $(x_1,y_1)$ is the lower left corner and $(x_2,y_2)$ is the upper right corner. All $x$ values will be distinct. All $y$ values will be distinct.

-----Output-----
Output a single integer, which is $1$ if some pair of rectangles intersect, $0$ if no pair of rectangles intersect.

-----Examples-----
Sample Input:
3
0 0 2 2
1 1 3 4
5 7 6 8
Sample Output:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bozo is shifting his house. He has some balls and boxes which he has to shift. He now wonders how large a ball he can fit in a given box. Given the dimensions of a box, help Bozo determine the radius of the largest ball that he can fit in the box. Assume that an inflated ball will be spherical.

Input:-

The first line of the input will be T, the number of test cases. Next follows T lines each containing three space separated integers (L, B, H) which are the length, breadth and height of the box respectively.

Output:-

Print T lines each consisting of the radius(correct to 1 decimal place) of the largest ball that Bozo can fit in the box of dimensions corresponding to each test case.

Constraints:

1 ≤ T ≤ 10^5 
1 ≤ L, B, H ≤ 10^18

SAMPLE INPUT
3
1 2 3
3 3 7
987548 4578445 9645875456

SAMPLE OUTPUT
0.5
1.5
493774.0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today, Chef has a fencing job at hand and has to fence up a surface covering N$N$ points. 
To minimize his work, he started looking for an algorithm that had him fence the least amount of length. 
He came up with the Convex Hull algorithm, but soon realized it gave him some random shape to fence. However, Chef likes rectangles and has a favourite number M$M$. 
Help him find the minimum perimeter he has to fence if he wants to fence a rectangle, with slope of one of the sides as M$M$, to cover all the points.

-----Input:-----
- The first line contains two integers N$N$ and M$M$, the number of points and the Chef's favourite Number.
- The next n lines contain two space separated integers X$X$ and Y$Y$, the coordinates of the point.

-----Output:-----
Print a single decimal number, denoting the perimeter of the rectangle. Answer will considered correct if it has absolute error less than 10−6$10^{-6}$.

-----Constraints-----
- 2≤N≤1000000$2 \leq N \leq 1000000$
- −1000≤M≤1000$-1000 \leq M \leq 1000$
- −1000000≤X≤1000000$-1000000 \leq X \leq 1000000$
- −1000000≤Y≤1000000$-1000000 \leq Y \leq 1000000$

-----Sample Input:-----
4 1
0 1
0 -1
1 0
-1 0

-----Sample Output:-----
5.656854249492380

-----Note:-----
- As the input size is large, it is recommended to use Fast IO.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once upon a time a child got a test consisting of multiple-choice questions as homework. A multiple-choice question consists of four choices: A, B, C and D. Each choice has a description, and the child should find out the only one that is correct.

Fortunately the child knows how to solve such complicated test. The child will follow the algorithm:

  If there is some choice whose description at least twice shorter than all other descriptions, or at least twice longer than all other descriptions, then the child thinks the choice is great.  If there is exactly one great choice then the child chooses it. Otherwise the child chooses C (the child think it is the luckiest choice). 

You are given a multiple-choice questions, can you predict child's choose?


-----Input-----

The first line starts with "A." (without quotes), then followed the description of choice A. The next three lines contains the descriptions of the other choices in the same format. They are given in order: B, C, D. Please note, that the description goes after prefix "X.", so the prefix mustn't be counted in description's length.

Each description is non-empty and consists of at most 100 characters. Each character can be either uppercase English letter or lowercase English letter, or "_". 


-----Output-----

Print a single line with the child's choice: "A", "B", "C" or "D" (without quotes).


-----Examples-----
Input
A.VFleaKing_is_the_author_of_this_problem
B.Picks_is_the_author_of_this_problem
C.Picking_is_the_author_of_this_problem
D.Ftiasch_is_cute

Output
D

Input
A.ab
B.abcde
C.ab
D.abc

Output
C

Input
A.c
B.cc
C.c
D.c

Output
B



-----Note-----

In the first sample, the first choice has length 39, the second one has length 35, the third one has length 37, and the last one has length 15. The choice D (length 15) is twice shorter than all other choices', so it is great choice. There is no other great choices so the child will choose D.

In the second sample, no choice is great, so the child will choose the luckiest choice C.

In the third sample, the choice B (length 2) is twice longer than all other choices', so it is great choice. There is no other great choices so the child will choose B.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two linked lists, the task is to complete the function findIntersection(), that returns the intersection of two linked lists. Each of the two linked list contains distinct node values.
Example 1:
Input:
LinkedList1: 9->6->4->2->3->8
LinkedList2: 1->2->8->6
Output: 6 2 8
Your Task:
You task is to complete the function findIntersection() which takes the heads of the 2 input linked lists as parameter and returns the head of intersection list. Returned list will be automatically printed by driver code.
Note: The order of nodes in this list should be same as the order in which those particular nodes appear in input list 1.
Constraints:
1 <= n,m <= 10^{4}
Expected time complexity: O(m+n)
Expected auxiliary space: O(m+n)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two sets, $\mbox{A}$ and $\mbox{B}$. 

Your job is to find whether set $\mbox{A}$ is a subset of set $\mbox{B}$.
 
If set $\mbox{A}$ is subset of set $\mbox{B}$, print True.

If set $\mbox{A}$ is not a subset of set $\mbox{B}$, print False.

Input Format

The first line will contain the number of test cases, $\mathbf{T}$. 

The first line of each test case contains the number of elements in set $\mbox{A}$.

The second line of each test case contains the space separated elements of set $\mbox{A}$.

The third line of each test case contains the number of elements in set $\mbox{B}$.

The fourth line of each test case contains the space separated elements of set $\mbox{B}$.

Constraints

$\textbf{0}<T<21$ 
$0<\text{Number of elements in each set}<1001$

Output Format

Output True or False for each test case on separate lines.

Sample Input
3
5
1 2 3 5 6
9
9 8 5 6 3 2 1 4 7
1
2
5
3 6 5 4 1
7
1 2 3 5 6 8 9
3
9 8 2

Sample Output
True 
False
False

Explanation

Test Case 01 Explanation

Set $\mbox{A}$ = {1 2 3 5 6} 

Set $\mbox{B}$ = {9 8 5 6 3 2 1 4 7} 

All the elements of set $\mbox{A}$ are elements of set $\mbox{B}$. 

Hence, set $\mbox{A}$ is a subset of set $\mbox{B}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has a strong stomach. He never gets a stomachache from eating something whose "best-by" date is at most X days earlier.
He gets a stomachache if the "best-by" date of the food is X+1 or more days earlier, though.
Other than that, he finds the food delicious if he eats it not later than the "best-by" date. Otherwise, he does not find it delicious.
Takahashi bought some food A days before the "best-by" date, and ate it B days after he bought it.
Write a program that outputs delicious if he found it delicious, safe if he did not found it delicious but did not get a stomachache either, and dangerous if he got a stomachache.

-----Constraints-----
 - 1 ≤ X,A,B ≤ 10^9

-----Input-----
Input is given from Standard Input in the following format:
X A B

-----Output-----
Print delicious if Takahashi found the food delicious; print safe if he neither found it delicious nor got a stomachache; print dangerous if he got a stomachache.

-----Sample Input-----
4 3 6

-----Sample Output-----
safe

He ate the food three days after the "best-by" date. It was not delicious or harmful for him.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An array in a certain programming language is defined in the following way:
 - The beginning and the end of an array is denoted by an open and closed curly bracket, respectively.
 - Inside the curly braces, there are (possibly even 0) values separated by a comma (there is no comma after the last value in the array).
 - Each value can be a word (an array of lowercase letters of the English alphabet) or another array.
 - Examples of correctly defined arrays are: “{}”, “{a,b,c}”, and “{abc,znj,{novi,niz},pozz}”.

Recently, you’ve noticed that the programming language does not throw an error if you do not place the appropriate number of spaces and new lines before or after the curly braces or the commas. Given the fact that you too mind the values being so “squished” together, you’ve decided to get to work and modify the shape of the array in the following way:
 - Each value that is not an array or denotes the beginning or the end of the array (curly braces) will be in its own line.
 - The commas are “connected” with the value located directly before them and there is a new line after each comma.
 - After the curly bracket denoting the beginning of the array, the indentation of the content increases (shifting the output to the right) for $2$ spaces.
 - Before the curly bracket denoting the end of the array ’}’, the indentation of the content decreases (shifting the output to the left) for $2$ spaces.

-----Input-----
The first line of input contains an array of characters $S$ ($1 \leq |S| \leq 1500$), representing the array from the task.

-----Output-----
The output must consist of the modified version of the array from the task.

-----Examples-----
Sample Input 1:
{abc,ono,sto}
Sample Output 1:
{
  abc,
  ono,
  sto
}

Sample Input 2:
{}
Sample Output 2:
{
}

Sample Input 3:
{znakovi}
Sample Output 3:
{
  znakovi
}

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