vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given integers A and B, each between 1 and 3 (inclusive).
Determine if there is an integer C between 1 and 3 (inclusive) such that A \times B \times C is an odd number.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq A, B \leq 3

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

-----Output-----
If there is an integer C between 1 and 3 that satisfies the condition, print Yes; otherwise, print No.

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

-----Sample Output-----
Yes

Let C = 3. Then, A \times B \times C = 3 \times 1 \times 3 = 9, which is an odd number.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
C： AA グラフ (AA Graph)

Problem

Given a graph as an ASCII Art (AA), please print the length of shortest paths from the vertex s to the vertex t. The AA of the graph satisfies the following constraints.

A vertex is represented by an uppercase alphabet and symbols `o` in 8 neighbors as follows.


ooo
oAo
ooo


Horizontal edges and vertical edges are represented by symbols `-` and `|`, respectively. Lengths of all edges are 1, that is, it do not depends on the number of continuous symbols `-` or `|`. All edges do not cross each other, and all vertices do not overlap and touch each other.

For each vertex, outgoing edges are at most 1 for each directions top, bottom, left, and right. Each edge is connected to a symbol `o` that is adjacent to an uppercase alphabet in 4 neighbors as follows.


..|..
.ooo.
-oAo-
.ooo.
..|..


Therefore, for example, following inputs are not given.


..........
.ooo..ooo.
.oAo..oBo.
.ooo--ooo.
..........


(Edges do not satisfies the constraint about their position.)


oooooo
oAooBo
oooooo


(Two vertices are adjacent each other.)

Input Format


H W s t
a_1
$\vdots$
a_H


* In line 1, two integers H and W, and two characters s and t are given. H and W is the width and height of the AA, respectively. s and t is the start and end vertices, respectively. They are given in separating by en spaces.
* In line 1 + i where 1 \leq i \leq H, the string representing line i of the AA is given.



Constraints

* 3 \leq H, W \leq 50
* s and t are selected by uppercase alphabets from `A` to `Z`, and s \neq t.
* a_i (1 \leq i \leq H) consists of uppercase alphabets and symbols `o`, `-`, `|`, and `.`.
* Each uppercase alphabet occurs at most once in the AA.
* It is guaranteed that there are two vertices representing s and t.
* The AA represents a connected graph.



Output Format

Print the length of the shortest paths from s to t in one line.

Example 1


14 16 A L
ooo.....ooo.....
oAo-----oHo.....
ooo.....ooo..ooo
.|.......|...oLo
ooo..ooo.|...ooo
oKo--oYo.|....|.
ooo..ooo.|....|.
.|....|.ooo...|.
.|....|.oGo...|.
.|....|.ooo...|.
.|....|.......|.
ooo..ooo.....ooo
oFo--oXo-----oEo
ooo..ooo.....ooo


Output 1


5

Exapmple 2


21 17 F L
.................
.....ooo.....ooo.
.....oAo-----oBo.
.....ooo.....ooo.
......|.......|..
.ooo..|..ooo..|..
.oCo..|..oDo.ooo.
.ooo.ooo.ooo.oEo.
..|..oFo..|..ooo.
..|..ooo..|...|..
..|...|...|...|..
..|...|...|...|..
..|...|...|...|..
.ooo.ooo.ooo..|..
.oGo-oHo-oIo..|..
.ooo.ooo.ooo..|..
..|...........|..
.ooo...ooo...ooo.
.oJo---oKo---oLo.
.ooo...ooo...ooo.
.................


Output 2


4





Example

Input




Output

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
------Read problems statements in Hindi,
Mandarin chinese
, Russian and Vietnamese as well. ------ 

Sheokand is good at mathematics. One day, to test his math skills, Kaali gave him an integer $N$. To impress Kaali, Sheokand has to convert $N$ into an integer $M$ that can be represented in the form $2^{x} + 2^{y}$ (where $x$ and $y$ are non-negative integers such that $x \neq y$). In order to do that, he can perform two types of operations:
add $1$ to $N$
subtract $1$ from $N$

However, Sheokand is preparing for his exams. Can you help him find the minimum number of operations required to convert $N$ into a valid integer $M$?

------  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 and only line of each testcase contains a single integer $N$.

------  Output ------
For each test case, print a single line containing one integer — the minimum required number of operations.

------  Constraints  ------
$1 ≤ T ≤ 100,000$
$1 ≤ N ≤ 10^{9}$

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ T ≤ 1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
3
10
22
4
----- Sample Output 1 ------ 
0
2
1
----- explanation 1 ------ 
Example case 1: $N=10$ is already in the form $2^{x} + 2^{y}$, with $x=3$ and $y=1$.

Example case 2: $N=22$ can be converted into $M=20=2^{2}+2^{4}$ or $M=24=2^{3}+2^{4}$ in two operations.

Example case 3: $N=4$ can be converted into $M=3=2^{0}+2^{1}$ or $M=5=2^{0}+2^{2}$ in one operation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let us define the score of an array B (B_{1}, B_{2}, B_{3},...,B_{k}) as:

\begin{equation}
score(B)=\begin{cases}
\sum_{i=1}^{k}B_{i}, & \text{if } k > 1 \text{ and } Max(B) - SecondMax(B) < X.\\
-\sum_{i=1}^{k}B_{i}, & \text{otherwise}.
\end{cases}
\end{equation}

Here, SecondMax(B) denotes the second element in B if we sort it in non-increasing order.

You are given an array A with N elements. You can partition it into multiple continuous subarrays, aiming to maximize the sum of the scores of each of the subarrays. Note that, in a partition, each element of the array belongs to exactly one subarray.

Additionally, you should perform Q queries. For each given value of X, find the maximum sum of score if you partition the array optimally.

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

- The first line contains T - the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and Q - the size of the array A and the number of queries.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.
- The third line contains Q space-separated integers X_{1}, X_{2}, \ldots, X_{Q}.

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

For each test case, output Q space-separated integers in a new line, the maximum sum of score you can obtain.

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 3\cdot 10^{5}$
$1 ≤ A_{i},X_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $3\cdot 10^{5}$.
- Sum of $Q$ over all test cases does not exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
2
5 3
1 4 3 6 2
1 4 2
5 2
5 7 10 1 1
2 3
----- Sample Output 1 ------ 
-16 16 0 
-20 4
----- explanation 1 ------ 
Test case $1$: In the third query of the first testcase, an optimal partition is $[1, 4, 3], [6, 2]$. The sum of score is $(1 + 4 + 3) - (6 + 2) = 0$.

Test case $2$: In the second query of the second testcase, an optimal partition is $[5, 7], [10], [1, 1]$. The sum of score is $(5 + 7) - (10) + (1 + 1) = 4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have three stacks of cylinders where each cylinder has the same diameter, but they may vary in height. You can change the height of a stack by removing and discarding its topmost cylinder any number of times. 

Find the maximum possible height of the stacks such that all of the stacks are exactly the same height. This means you must remove zero or more cylinders from the top of zero or more of the three stacks until they are all the same height, then return the height.  

Example  

$h1=[1,2,1,1]$ 

$h2=[1,1,2]$ 

$h3=[1,1]$  

There are $4,3$ and $2$ cylinders in the three stacks, with their heights in the three arrays.  Remove the top 2 cylinders from $\mbox{h1}$ (heights = [1, 2]) and from $h2$ (heights = [1, 1]) so that the three stacks all are 2 units tall.  Return $2$ as the answer.  

Note: An empty stack is still a stack.  

Function Description  

Complete the equalStacks function in the editor below.

equalStacks has the following parameters:  

int h1[n1]: the first array of heights  
int h2[n2]: the second array of heights  
int h3[n3]: the third array of heights  

Returns  

int: the height of the stacks when they are equalized  

Input Format

The first line contains three space-separated integers, $n\mbox{1}$, $n2$, and $n3$, the numbers of cylinders in stacks $1$, $2$, and $3$. The subsequent lines describe the respective heights of each cylinder in a stack from top to bottom:      

The second line contains $n1$ space-separated integers, the cylinder heights in stack $1$. The first element is the top cylinder of the stack.  
The third line contains $n2$ space-separated integers, the cylinder heights in stack $2$. The first element is the top cylinder of the stack.     
The fourth line contains $n3$ space-separated integers, the cylinder heights in stack $3$.    The first element is the top cylinder of the stack.  

Constraints

$0<n1,n2,n3\leq10^5$
$0<\:\textit{height of any cylinder}\leq100$

Sample Input
STDIN       Function
-----       --------
5 3 4       h1[] size n1 = 5, h2[] size n2 = 3, h3[] size n3 = 4  
3 2 1 1 1   h1 = [3, 2, 1, 1, 1]
4 3 2       h2 = [4, 3, 2]
1 1 4 1     h3 = [1, 1, 4, 1]

Sample Output
5

Explanation

Initially, the stacks look like this:

To equalize thier heights, remove the first cylinder from stacks $1$ and $2$, and then remove the top two cylinders from stack $3$ (shown below).

The stack heights are reduced as follows:

$8-3=5$
$9-4=5$
$7-1-1=5$

All three stacks now have $height=5$, the value to return.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Long ago, when Petya was a schoolboy, he was very much interested in the Petr# language grammar. During one lesson Petya got interested in the following question: how many different continuous substrings starting with the *s**begin* and ending with the *s**end* (it is possible *s**begin*<==<=*s**end*), the given string *t* has. Substrings are different if and only if their contents aren't equal, their positions of occurence don't matter. Petya wasn't quite good at math, that's why he couldn't count this number. Help him!

Input Specification:
The input file consists of three lines. The first line contains string *t*. The second and the third lines contain the *s**begin* and *s**end* identificators, correspondingly. All three lines are non-empty strings consisting of lowercase Latin letters. The length of each string doesn't exceed 2000 characters.

Output Specification:
Output the only number — the amount of different substrings of *t* that start with *s**begin* and end with *s**end*.

Demo Input:
['round\nro\nou\n', 'codeforces\ncode\nforca\n', 'abababab\na\nb\n', 'aba\nab\nba\n']

Demo Output:
['1\n', '0\n', '4\n', '1\n']

Note:
In the third sample there are four appropriate different substrings. They are: ab, abab, ababab, abababab.

In the fourth sample identificators intersect.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
An exam for *n* students will take place in a long and narrow room, so the students will sit in a line in some order. The teacher suspects that students with adjacent numbers (*i* and *i*<=+<=1) always studied side by side and became friends and if they take an exam sitting next to each other, they will help each other for sure.

Your task is to choose the maximum number of students and make such an arrangement of students in the room that no two students with adjacent numbers sit side by side.

Input Specification:
A single line contains integer *n* (1<=≤<=*n*<=≤<=5000) — the number of students at an exam.

Output Specification:
In the first line print integer *k* — the maximum number of students who can be seated so that no two students with adjacent numbers sit next to each other.

In the second line print *k* distinct integers *a*1,<=*a*2,<=...,<=*a**k* (1<=≤<=*a**i*<=≤<=*n*), where *a**i* is the number of the student on the *i*-th position. The students on adjacent positions mustn't have adjacent numbers. Formally, the following should be true: |*a**i*<=-<=*a**i*<=+<=1|<=≠<=1 for all *i* from 1 to *k*<=-<=1.

If there are several possible answers, output any of them.

Demo Input:
['6', '3\n']

Demo Output:
['6\n1 5 3 6 2 4', '2\n1 3']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You received a card at a banquet. On the card, a matrix of $N$ rows and $M$ columns and two integers $K$ and $S$ are written. All the elements in the matrix are integers, and an integer at the $i$-th row from the top and the $j$-th column from the left is denoted by $A_{i,j}$.

You can select up to $K$ elements from the matrix and invert the sign of the elements. If you can make a matrix such that there is no vertical or horizontal contiguous subsequence whose sum is greater than $S$, you can exchange your card for a prize.

Your task is to determine if you can exchange a given card for a prize.



Input

The input consists of a single test case of the following form.


$N$ $M$ $K$ $S$
$A_{1,1}$ $A_{1,2}$ ... $A_{1,M}$
:
$A_{N,1}$ $A_{N,2}$ ... $A_{N,M}$


The first line consists of four integers $N, M, K$ and $S$ ($1 \leq N, M \leq 10, 1 \leq K \leq 5, 1 \leq S \leq 10^6$). The following $N$ lines represent the matrix in your card. The ($i+1$)-th line consists of $M$ integers $A_{i,1}, A_{i,2}, ..., A_{i, M}$ ($-10^5 \leq A_{i,j} \leq 10^5$).

Output

If you can exchange your card for a prize, print 'Yes'. Otherwise, print 'No'.

Examples

Input

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


Output

Yes


Input

2 3 1 5
4 8 -2
-2 -5 -3


Output

Yes


Input

2 3 1 5
9 8 -2
-2 -5 -3


Output

No


Input

2 2 3 100
0 0
0 0


Output

Yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After overcoming the stairs Dasha came to classes. She needed to write a password to begin her classes. The password is a string of length n which satisfies the following requirements:  There is at least one digit in the string,  There is at least one lowercase (small) letter of the Latin alphabet in the string,  There is at least one of three listed symbols in the string: '#', '*', '&'.  [Image] 

Considering that these are programming classes it is not easy to write the password.

For each character of the password we have a fixed string of length m, on each of these n strings there is a pointer on some character. The i-th character displayed on the screen is the pointed character in the i-th string. Initially, all pointers are on characters with indexes 1 in the corresponding strings (all positions are numbered starting from one).

During one operation Dasha can move a pointer in one string one character to the left or to the right. Strings are cyclic, it means that when we move the pointer which is on the character with index 1 to the left, it moves to the character with the index m, and when we move it to the right from the position m it moves to the position 1.

You need to determine the minimum number of operations necessary to make the string displayed on the screen a valid password. 


-----Input-----

The first line contains two integers n, m (3 ≤ n ≤ 50, 1 ≤ m ≤ 50) — the length of the password and the length of strings which are assigned to password symbols. 

Each of the next n lines contains the string which is assigned to the i-th symbol of the password string. Its length is m, it consists of digits, lowercase English letters, and characters '#', '*' or '&'.

You have such input data that you can always get a valid password.


-----Output-----

Print one integer — the minimum number of operations which is necessary to make the string, which is displayed on the screen, a valid password. 


-----Examples-----
Input
3 4
1**2
a3*0
c4**

Output
1

Input
5 5
#*&#*
*a1c&
&q2w*
#a3c#
*&#*&

Output
3



-----Note-----

In the first test it is necessary to move the pointer of the third string to one left to get the optimal answer.  [Image] 

In the second test one of possible algorithms will be:   to move the pointer of the second symbol once to the right.  to move the pointer of the third symbol twice to the right.  [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Count the number of labeled strongly connected digraphs with the given number of vertices.  

Input Format 

The first line contains $\mathbf{T}$, the number of queries. 

Following are $\mathbf{T}$ lines. Each line contains one integer $N$, denoting the number of vertices.  

Output Format 

Output $\mathbf{T}$ lines. Each line is the number of labeled strongly connected digraphs with $N$ vertices, modulo $(10^9+7)$. 

Constraints 

$1\leq T\leq1000$ 

$1\leq N\leq1000$  

Sample Input

5
1
2
3
4
1000

Sample Output

1
1
18
1606
871606913

Explanation

You can refer to oeis.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
It is well known that the planet suffers from the energy crisis. Little Petya doesn't like that and wants to save the world. For this purpose he needs every accumulator to contain the same amount of energy. Initially every accumulator has some amount of energy: the *i*-th accumulator has *a**i* units of energy. Energy can be transferred from one accumulator to the other. Every time *x* units of energy are transferred (*x* is not necessarily an integer) *k* percent of it is lost. That is, if *x* units were transferred from one accumulator to the other, amount of energy in the first one decreased by *x* units and in other increased by  units.

Your task is to help Petya find what maximum equal amount of energy can be stored in each accumulator after the transfers.

Input Specification:
First line of the input contains two integers *n* and *k* (1<=≤<=*n*<=≤<=10000,<=0<=≤<=*k*<=≤<=99) — number of accumulators and the percent of energy that is lost during transfers.

Next line contains *n* integers *a*1,<=*a*2,<=... ,<=*a**n* — amounts of energy in the first, second, .., *n*-th accumulator respectively (0<=≤<=*a**i*<=≤<=1000,<=1<=≤<=*i*<=≤<=*n*).

Output Specification:
Output maximum possible amount of energy that can remain in each of accumulators after the transfers of energy.

The absolute or relative error in the answer should not exceed 10<=-<=6.

Demo Input:
['3 50\n4 2 1\n', '2 90\n1 11\n']

Demo Output:
['2.000000000\n', '1.909090909\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pieguy and Piegirl are playing a game. They have a rooted binary tree, that has a property that each node is either a leaf or has exactly two children. Each leaf has a number associated with it.

On his/her turn a player can choose any two leafs that share their immediate parent, remove them, and associate either of their values with their parent, that now became a leaf (the player decides which of the two values to associate). The game ends when only one node (the one that was the root of the tree) is left.

Pieguy goes first, and his goal is to maximize the value that will be associated with the root when the game ends. Piegirl wants to minimize that value. Assuming that both players are playing optimally, what number will be associated with the root when the game ends?

Input

First line contains a single integer t (1 ≤ t ≤ 100) — number of test cases. Then t test cases follow. Each test case begins with an empty line, followed by a line with a single integer n (1 ≤ n ≤ 250), followed by n lines describing n nodes of the tree. Each of those n lines either contains a non-negative number ai, indicating a leaf node with value ai (0 ≤ ai ≤ 1000) associated with it, or  - 1 followed by integers l and r, indicating a non-leaf node with children l and r (0 ≤ l, r ≤ n - 1). Nodes are numbered from 0 to n - 1. The root is always node 0.

Output

For each test case print one line with one integer on it — the number that will be associated with the root when the game ends.

Examples

Input

4

3
-1 1 2
10
5

5
-1 1 2
-1 3 4
10
5
20

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

11
-1 1 2
-1 3 4
-1 5 6
-1 7 8
15
7
-1 9 10
7
8
9
11


Output

10
10
4
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Miniature Toy Association (or MTA for short) is releasing the latest edition of its brand of collectible figurines. MTA used to sell them individually, but now has decided to adopt a new business strategy that involves randomly choosing $4$ figurines from the entire collection to be packaged and sold together as a ‘$4$-pack’. Each figurine in a $4$-pack is chosen independently and randomly with uniform distribution. As such, it is possible that a $4$-pack may contain multiple copies of a particular figurine.

Even though some figurines may be more valuable than others, every randomly assembled $4$-pack is sold at the same price. Customers buying a $4$-pack of figurines do not know ahead of time which figurines will be inside, and so it is a matter of chance whether they get the figurines that they want most. While the price is the same across all $4$-packs, the weight is not, as each figurine has a distinct integer weight in grams.

Before MTA releases its new line of figurines, its Chief Financial Officer (CFO) would like an executive summary with information about the proposed $4$-packs. Specifically, the CFO wants to know: the greatest possible weight of a $4$-pack, the smallest possible weight of a $4$-pack, the number of distinct weights that a $4$-pack could have, and the expected weight of a $4$-pack. Note that the expected weight is the average (mean) weight across all possible distinct $4$-packs, where two $4$-packs are distinct if and only if one $4$-pack has a different number of figurines of any particular weight than the other $4$-pack. So, for example, a $4$-pack with weights $\{ 2,2,3,5\} $ is distinct from a $4$-pack with weights $\{ 2,3,3,4\} $ (even though they both have the same total weight). Also, a $4$-pack with weights $\{ 2,2,3,5\} $ is distinct from a 4-pack with weights $\{ 2,3,3,5\} $.

-----Input-----
The input consists of a single test case. The first line of the input contains a single integer $N$, the number of different figurines to be produced, where $1\leq N\leq 40000$. The next line contains $N$ space-separated integers representing the weight in grams of each of the figurines. Each weight, $k$, is an integer satisfying $1\leq k\leq 60000$, and all $N$ weights are distinct.

-----Output-----
The output should consist of a single line with $4$ space-separated values. The first value should be an integer, the maximum weight of a $4$-pack in grams for the given set of figurines. The second value should be an integer, the minimum weight of a $4$-pack in grams for the given set of figurines. The third value should be an integer, the number of distinct weights that the $4$-packs can have for the given set of figurines. The fourth value should be a floating-point value, the expected weight of a $4$-pack in grams for the given set of figurines, with an absolute or relative error of at most $10^{-4}$.

-----Examples-----
Sample Input:
4
1 2 4 7
Sample Output:
28 4 21 14.0

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