vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
After a revolution in Berland the new dictator faced an unexpected challenge: the country has to be somehow ruled. The dictator is a very efficient manager, yet he can't personally give orders to each and every citizen. That's why he decided to pick some set of leaders he would control. Those leaders will directly order the citizens. However, leadership efficiency turned out to vary from person to person (i.e. while person A makes an efficient leader, person B may not be that good at it). That's why the dictator asked world-famous berland scientists for help. The scientists suggested an innovatory technology — to make the leaders work in pairs.

A relationship graph is some undirected graph whose vertices correspond to people. A simple path is a path with no repeated vertices. Long and frighteningly expensive research showed that a pair of people has maximum leadership qualities if a graph of relationships has a simple path between them with an odd number of edges. The scientists decided to call such pairs of different people leader pairs. Secret services provided the scientists with the relationship graph so that the task is simple — we have to learn to tell the dictator whether the given pairs are leader pairs or not. Help the scientists cope with the task.

Input

The first line contains integers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) — the number of vertices and edges in the relationship graph correspondingly. Next m lines contain pairs of integers a and b which mean that there is an edge between the a-th and the b-th vertices (the vertices are numbered starting from 1, 1 ≤ a, b ≤ n). It is guaranteed that the graph has no loops or multiple edges.

Next line contains number q (1 ≤ q ≤ 105) — the number of pairs the scientists are interested in. Next q lines contain these pairs (in the same format as the edges, the queries can be repeated, a query can contain a pair of the identical vertices).

Output

For each query print on a single line "Yes" if there's a simple odd path between the pair of people; otherwise, print "No".

Examples

Input

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


Output

No
Yes
Yes
Yes
No
Yes
Yes
Yes

Note

Notes to the samples:

1) Between vertices 1 and 2 there are 2 different simple paths in total: 1-3-2 and 1-4-2. Both of them consist of an even number of edges. 

2) Vertices 1 and 3 are connected by an edge, that's why a simple odd path for them is 1-3.

5) Vertices 1 and 5 are located in different connected components, there's no path between them.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* psychos standing in a line. Each psycho is assigned a unique integer from 1 to *n*. At each step every psycho who has an id greater than the psycho to his right (if exists) kills his right neighbor in the line. Note that a psycho might kill and get killed at the same step. 

You're given the initial arrangement of the psychos in the line. Calculate how many steps are needed to the moment of time such, that nobody kills his neighbor after that moment. Look notes to understand the statement more precise.

Input Specification:
The first line of input contains integer *n* denoting the number of psychos, (1<=≤<=*n*<=≤<=105). In the second line there will be a list of *n* space separated distinct integers each in range 1 to *n*, inclusive — ids of the psychos in the line from left to right.

Output Specification:
Print the number of steps, so that the line remains the same afterward.

Demo Input:
['10\n10 9 7 8 6 5 3 4 2 1\n', '6\n1 2 3 4 5 6\n']

Demo Output:
['2\n', '0\n']

Note:
In the first sample line of the psychos transforms as follows: [10 9 7 8 6 5 3 4 2 1]  →  [10 8 4]  →  [10]. So, there are two steps.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Unfortunately, not all numbers are lucky. Petya calls a number nearly lucky if the number of lucky digits in it is a lucky number. He wonders whether number *n* is a nearly lucky number.

Input Specification:
The only line contains an integer *n* (1<=≤<=*n*<=≤<=1018).

Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

Output Specification:
Print on the single line "YES" if *n* is a nearly lucky number. Otherwise, print "NO" (without the quotes).

Demo Input:
['40047\n', '7747774\n', '1000000000000000000\n']

Demo Output:
['NO\n', 'YES\n', 'NO\n']

Note:
In the first sample there are 3 lucky digits (first one and last two), so the answer is "NO".

In the second sample there are 7 lucky digits, 7 is lucky number, so the answer is "YES".

In the third sample there are no lucky digits, so the answer is "NO".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valera has got n domino pieces in a row. Each piece consists of two halves — the upper one and the lower one. Each of the halves contains a number from 1 to 6. Valera loves even integers very much, so he wants the sum of the numbers on the upper halves and the sum of the numbers on the lower halves to be even.

To do that, Valera can rotate the dominoes by 180 degrees. After the rotation the upper and the lower halves swap places. This action takes one second. Help Valera find out the minimum time he must spend rotating dominoes to make his wish come true.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100), denoting the number of dominoes Valera has. Next n lines contain two space-separated integers x_{i}, y_{i} (1 ≤ x_{i}, y_{i} ≤ 6). Number x_{i} is initially written on the upper half of the i-th domino, y_{i} is initially written on the lower half.


-----Output-----

Print a single number — the minimum required number of seconds. If Valera can't do the task in any time, print  - 1.


-----Examples-----
Input
2
4 2
6 4

Output
0

Input
1
2 3

Output
-1

Input
3
1 4
2 3
4 4

Output
1



-----Note-----

In the first test case the sum of the numbers on the upper halves equals 10 and the sum of the numbers on the lower halves equals 6. Both numbers are even, so Valera doesn't required to do anything.

In the second sample Valera has only one piece of domino. It is written 3 on the one of its halves, therefore one of the sums will always be odd.

In the third case Valera can rotate the first piece, and after that the sum on the upper halves will be equal to 10, and the sum on the lower halves will be equal to 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You must have tried to solve the Rubik’s cube. You might even have succeeded at it. Rubik’s cube is a 3x3x3 cube which has 6 different color for each face.The Rubik’s cube is made from 26 smaller pieces which are called cubies. There are 6 cubies at the centre of each face and these comprise of a single color. There are 8 cubies at the 8 corners which comprise of exactly 3 colors. The 12 reamaining cubies comprise of exactly 2 colors.

Apple has come up with a variation of the Rubik’s Cube, it’s the Rubik’s cuboid which has different colors on its 6 faces. The Rubik’s Cuboid comes in various sizes represented by M x N x O (M,N,O are natural numbers). Apple is giving away 100 Rubik’s cuboid for free to people who can answer a simple questions. Apple wants to know, in a Rubik’s cuboid with arbitrary dimensions, how many cubies would be there, which comprise of exactly 2 color.

-----Input-----
The input contains several test cases.The first line of the input contains an integer T denoting the number of test cases.

Each test case comprises of 3 natural numbers, M,N & O, which denote the dimensions of the Rubiks Cuboid.

-----Output-----
For each test case you are required to output the number of  cubies which comprise of 2 squares, each of which is of a different color.

-----Constraints-----
- 1 ≤ T ≤ <1000
- 1 ≤ M ≤ <100000
- 1 ≤ N ≤ <100000
- 1 ≤ O ≤ <100000

-----Example-----
Input:
1
3
3
3

Output:

12

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Dreamoon is standing at the position 0 on a number line. Drazil is sending a list of commands through Wi-Fi to Dreamoon's smartphone and Dreamoon follows them.

Each command is one of the following two types: 
 1.  Go 1 unit towards the positive direction, denoted as '+' 1.  Go 1 unit towards the negative direction, denoted as '-' 
But the Wi-Fi condition is so poor that Dreamoon's smartphone reports some of the commands can't be recognized and Dreamoon knows that some of them might even be wrong though successfully recognized. Dreamoon decides to follow every recognized command and toss a fair coin to decide those unrecognized ones (that means, he moves to the 1 unit to the negative or positive direction with the same probability 0.5). 

You are given an original list of commands sent by Drazil and list received by Dreamoon. What is the probability that Dreamoon ends in the position originally supposed to be final by Drazil's commands?

Input Specification:
The first line contains a string *s*1 — the commands Drazil sends to Dreamoon, this string consists of only the characters in the set {'+', '-'}. 

The second line contains a string *s*2 — the commands Dreamoon's smartphone recognizes, this string consists of only the characters in the set {'+', '-', '?'}. '?' denotes an unrecognized command.

Lengths of two strings are equal and do not exceed 10.

Output Specification:
Output a single real number corresponding to the probability. The answer will be considered correct if its relative or absolute error doesn't exceed 10<=-<=9.

Demo Input:
['++-+-\n+-+-+\n', '+-+-\n+-??\n', '+++\n??-\n']

Demo Output:
['1.000000000000\n', '0.500000000000\n', '0.000000000000\n']

Note:
For the first sample, both *s*<sub class="lower-index">1</sub> and *s*<sub class="lower-index">2</sub> will lead Dreamoon to finish at the same position  + 1. 

For the second sample, *s*<sub class="lower-index">1</sub> will lead Dreamoon to finish at position 0, while there are four possibilites for *s*<sub class="lower-index">2</sub>: {"+-++", "+-+-", "+--+", "+---"} with ending position {+2, 0, 0, -2} respectively. So there are 2 correct cases out of 4, so the probability of finishing at the correct position is 0.5. 

For the third sample, *s*<sub class="lower-index">2</sub> could only lead us to finish at positions {+1, -1, -3}, so the probability to finish at the correct position  + 3 is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Daisy loves playing games with words. Recently, she has been playing the following Deletive Editing word game with Daniel.

Daisy picks a word, for example, "DETERMINED". On each game turn, Daniel calls out a letter, for example, 'E', and Daisy removes the first occurrence of this letter from the word, getting "DTERMINED". On the next turn, Daniel calls out a letter again, for example, 'D', and Daisy removes its first occurrence, getting "TERMINED". They continue with 'I', getting "TERMNED", with 'N', getting "TERMED", and with 'D', getting "TERME". Now, if Daniel calls out the letter 'E', Daisy gets "TRME", but there is no way she can get the word "TERM" if they start playing with the word "DETERMINED".

Daisy is curious if she can get the final word of her choice, starting from the given initial word, by playing this game for zero or more turns. Your task it help her to figure this out.


-----Input-----

The first line of the input contains an integer $n$ — the number of test cases ($1 \le n \le 10000$). The following $n$ lines contain test cases.

Each test case consists of two words $s$ and $t$ separated by a space. Each word consists of at least one and at most 30 uppercase English letters; $s$ is the Daisy's initial word for the game; $t$ is the final word that Daisy would like to get at the end of the game.


-----Output-----

Output $n$ lines to the output — a single line for each test case. Output "YES" if it is possible for Daisy to get from the initial word $s$ to the final word $t$ by playing the Deletive Editing game. Output "NO" otherwise.


-----Examples-----

Input
6
DETERMINED TRME
DETERMINED TERM
PSEUDOPSEUDOHYPOPARATHYROIDISM PEPA
DEINSTITUTIONALIZATION DONATION
CONTEST CODE
SOLUTION SOLUTION
Output
YES
NO
NO
YES
NO
YES


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya is very upset that many people on the Net mix uppercase and lowercase letters in one word. That's why he decided to invent an extension for his favorite browser that would change the letters' register in every word so that it either only consisted of lowercase letters or, vice versa, only of uppercase ones. At that as little as possible letters should be changed in the word. For example, the word HoUse must be replaced with house, and the word ViP — with VIP. If a word contains an equal number of uppercase and lowercase letters, you should replace all the letters with lowercase ones. For example, maTRIx should be replaced by matrix. Your task is to use the given method on one given word.

Input

The first line contains a word s — it consists of uppercase and lowercase Latin letters and possesses the length from 1 to 100.

Output

Print the corrected word s. If the given word s has strictly more uppercase letters, make the word written in the uppercase register, otherwise - in the lowercase one.

Examples

Input

HoUse


Output

house


Input

ViP


Output

VIP


Input

maTRIx


Output

matrix

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hexagonal numbers are figurate numbers which can be calculated using the formula hn = 2n2 - n. You are given n; calculate n-th hexagonal number.

Input

The only line of input contains an integer n (1 ≤ n ≤ 100).

Output

Output the n-th hexagonal number.

Examples

Input

2


Output

6


Input

5


Output

45

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given two strings *a* and *b*. You have to remove the minimum possible number of consecutive (standing one after another) characters from string *b* in such a way that it becomes a subsequence of string *a*. It can happen that you will not need to remove any characters at all, or maybe you will have to remove all of the characters from *b* and make it empty.

Subsequence of string *s* is any such string that can be obtained by erasing zero or more characters (not necessarily consecutive) from string *s*.

Input Specification:
The first line contains string *a*, and the second line — string *b*. Both of these strings are nonempty and consist of lowercase letters of English alphabet. The length of each string is no bigger than 105 characters.

Output Specification:
On the first line output a subsequence of string *a*, obtained from *b* by erasing the minimum number of consecutive characters.

If the answer consists of zero characters, output «-» (a minus sign).

Demo Input:
['hi\nbob\n', 'abca\naccepted\n', 'abacaba\nabcdcba\n']

Demo Output:
['-\n', 'ac\n', 'abcba\n']

Note:
In the first example strings *a* and *b* don't share any symbols, so the longest string that you can get is empty.

In the second example ac is a subsequence of *a*, and at the same time you can obtain it by erasing consecutive symbols cepted from string *b*.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We will call a string that can be obtained by concatenating two equal strings an even string.
For example, xyzxyz and aaaaaa are even, while ababab and xyzxy are not.
You are given an even string S consisting of lowercase English letters.
Find the length of the longest even string that can be obtained by deleting one or more characters from the end of S.
It is guaranteed that such a non-empty string exists for a given input.

-----Constraints-----
 - 2 \leq |S| \leq 200
 - S is an even string consisting of lowercase English letters.
 - There exists a non-empty even string that can be obtained by deleting one or more characters from the end of S.

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the length of the longest even string that can be obtained.

-----Sample Input-----
abaababaab

-----Sample Output-----
6

 - abaababaab itself is even, but we need to delete at least one character.
 - abaababaa is not even.
 - abaababa is not even.
 - abaabab is not even.
 - abaaba is even. Thus, we should print its length, 6.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
The hero of our story, Valera, and his best friend Arcady are still in school, and therefore they spend all the free time playing turn-based strategy "GAGA: Go And Go Again". The gameplay is as follows. 

There are two armies on the playing field each of which consists of *n* men (*n* is always even). The current player specifies for each of her soldiers an enemy's soldier he will shoot (a target) and then all the player's soldiers shot simultaneously. This is a game world, and so each soldier shoots perfectly, that is he absolutely always hits the specified target. If an enemy soldier is hit, he will surely die. It may happen that several soldiers had been indicated the same target. Killed soldiers do not participate in the game anymore. 

The game "GAGA" consists of three steps: first Valera makes a move, then Arcady, then Valera again and the game ends. 

You are asked to calculate the maximum total number of soldiers that may be killed during the game.

Input Specification:
The input data consist of a single integer *n* (2<=≤<=*n*<=≤<=108, *n* is even). Please note that before the game starts there are 2*n* soldiers on the fields.

Output Specification:
Print a single number — a maximum total number of soldiers that could be killed in the course of the game in three turns.

Demo Input:
['2\n', '4\n']

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

Note:
The first sample test:

1) Valera's soldiers 1 and 2 shoot at Arcady's soldier 1.

2) Arcady's soldier 2 shoots at Valera's soldier 1.

3) Valera's soldier 1 shoots at Arcady's soldier 2.

There are 3 soldiers killed in total: Valera's soldier 1 and Arcady's soldiers 1 and 2.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Bob wants to put a new bargaining table in his office. To do so he measured the office room thoroughly and drew its plan: Bob's office room is a rectangular room *n*<=×<=*m* meters. Each square meter of the room is either occupied by some furniture, or free. A bargaining table is rectangular, and should be placed so, that its sides are parallel to the office walls. Bob doesn't want to change or rearrange anything, that's why all the squares that will be occupied by the table should be initially free. Bob wants the new table to sit as many people as possible, thus its perimeter should be maximal. Help Bob find out the maximum possible perimeter of a bargaining table for his office.

Input Specification:
The first line contains 2 space-separated numbers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=25) — the office room dimensions. Then there follow *n* lines with *m* characters 0 or 1 each. 0 stands for a free square meter of the office room. 1 stands for an occupied square meter. It's guaranteed that at least one square meter in the room is free.

Output Specification:
Output one number — the maximum possible perimeter of a bargaining table for Bob's office room.

Demo Input:
['3 3\n000\n010\n000\n', '5 4\n1100\n0000\n0000\n0000\n0000\n']

Demo Output:
['8\n', '16\n']

Note:
none

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

The tool min returns the minimum value along a given axis.

import numpy

my_array = numpy.array([[2, 5], 
                        [3, 7],
                        [1, 3],
                        [4, 0]])

print numpy.min(my_array, axis = 0)         #Output : [1 0]
print numpy.min(my_array, axis = 1)         #Output : [2 3 1 0]
print numpy.min(my_array, axis = None)      #Output : 0
print numpy.min(my_array)                   #Output : 0

By default, the axis value is None. Therefore, it finds the minimum over all the dimensions of the input array.    

 max 

The tool max returns the maximum value along a given axis.

import numpy

my_array = numpy.array([[2, 5], 
                        [3, 7],
                        [1, 3],
                        [4, 0]])

print numpy.max(my_array, axis = 0)         #Output : [4 7]
print numpy.max(my_array, axis = 1)         #Output : [5 7 3 4]
print numpy.max(my_array, axis = None)      #Output : 7
print numpy.max(my_array)                   #Output : 7

By default, the axis value is None. Therefore, it finds the maximum over all the dimensions of the input array.    

Task  

You are given a 2-D array with dimensions $N$X$\mbox{M}$. 

Your task is to perform the min function over axis $\mbox{I}$ and then find the max of that.

Input Format

The first line of input contains the space separated values of $N$ and $\mbox{M}$. 

The next $N$ lines contains $\mbox{M}$ space separated integers.

Output Format

Compute the min along axis $\mbox{I}$ and then print the max of that result. 

Sample Input
4 2
2 5
3 7
1 3
4 0

Sample Output
3

Explanation

The min along axis $\mbox{I}$ = $[2,3,1,0]$ 

The max of $[2,3,1,0]$ = $3$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We all know how great ABD aka AB-DE-VILLIERS is. However his team mates were jealous of him and posed a problem for him to solve.The problem description is as follows :

Given an array of integers,find the length of the largest subarray(contiguous) of the given array with the maximum possible GCD (Greatest Common Divisor).

For info on GCD ,see this link: https://en.wikipedia.org/wiki/Greatest_common_divisor

GCD of the subarray is defined as the GCD of all the elements of the subarray.
As ABD is not aware of competitive programming he asks your help. Help him!

-----Input-----
First line will contain integer N denoting the size of array.

Second line will contain N integers denoting array elements.

-----Output-----
The answer as specified in the problem statement .

-----Constraints-----
1 <= N <= 1000000

1 <= array[i] <=100000000000

-----Example-----
Input:
4
2 4 8 3

Output:
1

Explanation
GCD of all possible subarrays of the given array are : 2 , 2 , 2 , 1 , 4 , 4, 1 , 8 , 1 , 3

Largest GCD possible : 8

Length of the largest subarray with GCD as 8 is 1

Hence answer is 1 .

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