vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Lindsey Buckingham told Stevie Nicks "Go your own way". Nicks is now sad and wants to go away as quickly as possible, but she lives in a 2D hexagonal world.

Consider a hexagonal tiling of the plane as on the picture below. [Image] 

Nicks wishes to go from the cell marked $(0, 0)$ to a certain cell given by the coordinates. She may go from a hexagon to any of its six neighbors you want, but there is a cost associated with each of them. The costs depend only on the direction in which you travel. Going from $(0, 0)$ to $(1, 1)$ will take the exact same cost as going from $(-2, -1)$ to $(-1, 0)$. The costs are given in the input in the order $c_1$, $c_2$, $c_3$, $c_4$, $c_5$, $c_6$ as in the picture below. [Image] 

Print the smallest cost of a path from the origin which has coordinates $(0, 0)$ to the given cell.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^{4}$). Description of the test cases follows.

The first line of each test case contains two integers $x$ and $y$ ($-10^{9} \le x, y \le 10^{9}$) representing the coordinates of the target hexagon.

The second line of each test case contains six integers $c_1$, $c_2$, $c_3$, $c_4$, $c_5$, $c_6$ ($1 \le c_1, c_2, c_3, c_4, c_5, c_6 \le 10^{9}$) representing the six costs of the making one step in a particular direction (refer to the picture above to see which edge is for each value).


-----Output-----

For each testcase output the smallest cost of a path from the origin to the given cell.


-----Example-----
Input
2
-3 1
1 3 5 7 9 11
1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Output
18
1000000000000000000



-----Note-----

The picture below shows the solution for the first sample. The cost $18$ is reached by taking $c_3$ 3 times and $c_2$ once, amounting to $5+5+5+3=18$. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everybody knows that we have been living in the Matrix for a long time. And in the new seventh Matrix the world is ruled by beavers.

So let's take beaver Neo. Neo has so-called "deja vu" outbursts when he gets visions of events in some places he's been at or is going to be at. Let's examine the phenomenon in more detail.

We can say that Neo's city is represented by a directed graph, consisting of n shops and m streets that connect the shops. No two streets connect the same pair of shops (besides, there can't be one street from A to B and one street from B to A). No street connects a shop with itself. As Neo passes some streets, he gets visions. No matter how many times he passes street k, every time he will get the same visions in the same order. A vision is a sequence of shops.

We know that Neo is going to get really shocked if he passes the way from some shop a to some shop b, possible coinciding with a, such that the list of visited shops in the real life and in the visions coincide.

Suggest beaver Neo such path of non-zero length. Or maybe you can even count the number of such paths modulo 1000000007 (109 + 7)?..

Input

The first line contains integers n and m — the number of shops and the number of streets, correspondingly, 1 ≤ n ≤ 50, <image>. Next m lines contain the descriptions of the streets in the following format: xi yi ki v1 v2 ... vk, where xi and yi (1 ≤ xi, yi ≤ n, xi ≠ yi) are indices of shops connected by a street, ki (0 ≤ ki ≤ n) is the number of visions on the way from xi to yi; v1, v2, ..., vk (1 ≤ vi ≤ n) describe the visions: the numbers of the shops Neo saw. Note that the order of the visions matters.

It is guaranteed that the total number of visions on all streets doesn't exceed 105.

  * to get 50 points, you need to find any (not necessarily simple) path of length at most 2·n, that meets the attributes described above (subproblem E1); 
  * to get 50 more points, you need to count for each length from 1 to 2·n the number of paths that have the attribute described above (subproblem E2). 

Output

Subproblem E1. In the first line print an integer k (1 ≤ k ≤ 2·n) — the numbers of shops on Neo's path. In the next line print k integers — the number of shops in the order Neo passes them. If the graph doesn't have such paths or the length of the shortest path includes more than 2·n shops, print on a single line 0.

Subproblem E2. Print 2·n lines. The i-th line must contain a single integer — the number of required paths of length i modulo 1000000007 (109 + 7).

Examples

Input

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


Output

4
6 1 2 3


Input

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


Output

1
2
1
1
2
1
1
2
1
1
2
1

Note

The input in both samples are the same. The first sample contains the answer to the first subproblem, the second sample contains the answer to the second subproblem.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have been given a String S consisting of uppercase and lowercase English alphabets. You need to change the case of each alphabet in this String. That is, all the uppercase letters should be converted to lowercase and all the lowercase letters should be converted to uppercase. You need to then print the resultant String to output.

Input Format
The first and only line of input contains the String S  

Output Format
Print the resultant String on a single line.   

Constraints
 1 ≤ |S| ≤ 100   where |S|  denotes the length of string S.  

SAMPLE INPUT
abcdE

SAMPLE OUTPUT
ABCDe

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Almir had a small sequence $A_1, A_2, \ldots, A_N$. He decided to make $K$ copies of this sequence and concatenate them, forming a sequence $X_1, X_2, \ldots, X_{NK}$; for each valid $i$ and $j$ ($0 \le j < K$), $X_{j \cdot N + i} = A_i$.
For example, if $A = (1, 2, 3)$ and $K = 4$, the final sequence is $X = (1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3)$.
A pair $(i, j)$, where $1 \le i < j \le N$, is an inversion if $X_i > X_j$. Find the number of inversions in the final sequence $X$.

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

-----Output-----
For each test case, print a single line containing one integer ― the number of inversions in the sequence $X$.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 100$
- $1 \le K \le 10^6$
- $1 \le A_i \le 10^9$ for each valid $i$

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

-----Example Input-----
2
3 3
2 1 3
4 100
99 2 1000 24

-----Example Output-----
12
30000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $s$. And you have a function $f(x)$ defined as:
f(x) = 1, if $x$ is a vowel
f(x) = 0, if $x$ is a constant

Your task is to apply the above function on all the characters in the string s and convert 
the obtained binary string in decimal number $M$.
Since the number $M$ can be very large, compute it modulo $10^9+7$. 

-----Input:-----
- The first line of the input contains a single integer $T$ i.e the no. of test cases. 
- Each test line contains one String $s$ composed of lowercase English alphabet letters. 

-----Output:-----
For each case, print a single line containing one integer $M$ modulo $10^9 + 7$.

-----Constraints-----
- $1 ≤ T ≤ 50$
- $|s|≤10^5$

-----Subtasks-----
- 20 points : $|s|≤30$
- 80 points : $ \text{original constraints}$

-----Sample Input:-----
1
hello

-----Sample Output:-----
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have given a non-empty string. This string can consist of lowercase and uppercase english alphabets. Convert the string into an alternating sequence of lowercase and uppercase characters without changing the character at the 0th index.
Example 1:
Input:
S = "geeksforgeeks"
Output: gEeKsFoRgEeKs
Explanation: The first character is kept
unchanged whereas all the characters are
arranged in alternating order of lowercase
and uppercase.
Ã¢â¬â¹Example 2:
Input: 
S = "Geeksforgeeks"
Output: GeEkSfOrGeEkS
Explanation: The first character is kept
unchanged whereas all the characters are
arranged in alternating order of lowercase
and uppercase.
Your Task:
You don't need to read input or print anything. Your task is to complete the function getCrazy() which takes the string S as input and returns the resultant string by making the stated modifications.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1<=|S|<=10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Piegirl was asked to implement two table join operation for distributed database system, minimizing the network traffic.

Suppose she wants to join two tables, A and B. Each of them has certain number of rows which are distributed on different number of partitions. Table A is distributed on the first cluster consisting of m partitions. Partition with index i has a_{i} rows from A. Similarly, second cluster containing table B has n partitions, i-th one having b_{i} rows from B. 

In one network operation she can copy one row from any partition to any other partition. At the end, for each row from A and each row from B there should be a partition that has both rows. Determine the minimal number of network operations to achieve this.


-----Input-----

First line contains two integer numbers, m and n (1 ≤ m, n ≤ 10^5). Second line contains description of the first cluster with m space separated integers, a_{i} (1 ≤ a_{i} ≤ 10^9). Similarly, third line describes second cluster with n space separated integers, b_{i} (1 ≤ b_{i} ≤ 10^9).


-----Output-----

Print one integer — minimal number of copy operations.


-----Examples-----
Input
2 2
2 6
3 100

Output
11

Input
2 3
10 10
1 1 1

Output
6



-----Note-----

In the first example it makes sense to move all the rows to the second partition of the second cluster which is achieved in 2 + 6 + 3 = 11 operations

In the second example Piegirl can copy each row from B to the both partitions of the first cluster which needs 2·3 = 6 copy operations.

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

AOR Ika-chan is taking a class where grades are determined only by the score of the $ N $ report. AOR Ika-chan has $ M $ friends who are taking the same class, and if you have a report on a theme that you are not good at, you can get the same score as that friend by copying the report of a friend who is good at that theme. .. However, the teacher should not be aware that you are copying someone else's report, so you have to finish the report yourself, not copying someone else's report at least $ K $ out of $ N $ times. Also, AOR Ika didn't want to bother her friends, so she decided to copy the report to her friend $ i $ less than $ T_i $ times. Answer the maximum total score that AOR Ika can get when given the score when AOR Ika finishes the report by herself and the score when her friend finishes the report.



input

Input is given from standard input in the following format.

$ N \ M \ K $
$ a_1 \ \ cdots \ a_N $
$ b_ {11} \ \ cdots \ b_ {1N} $
$ \ vdots $
$ b_ {M1} \ \ cdots \ b_ {MN} $
$ T_1 \ \ cdots \ T_M $

$ a_i $ is the score when AOR Ika finishes the $ i $ th report, and $ b_ {ij} $ is the score when friend $ i $ finishes the $ j $ th report.

output

Output the maximum total score that AOR Ika can get. Also, output a line break at the end.

Example

Input

3 2 2
50 65 70
80 100 80
90 65 45
1 1


Output

225

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* pictures delivered for the new exhibition. The *i*-th painting has beauty *a**i*. We know that a visitor becomes happy every time he passes from a painting to a more beautiful one.

We are allowed to arranged pictures in any order. What is the maximum possible number of times the visitor may become happy while passing all pictures from first to last? In other words, we are allowed to rearrange elements of *a* in any order. What is the maximum possible number of indices *i* (1<=≤<=*i*<=≤<=*n*<=-<=1), such that *a**i*<=+<=1<=&gt;<=*a**i*.

Input Specification:
The first line of the input contains integer *n* (1<=≤<=*n*<=≤<=1000) — the number of painting.

The second line contains the sequence *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=1000), where *a**i* means the beauty of the *i*-th painting.

Output Specification:
Print one integer — the maximum possible number of neighbouring pairs, such that *a**i*<=+<=1<=&gt;<=*a**i*, after the optimal rearrangement.

Demo Input:
['5\n20 30 10 50 40\n', '4\n200 100 100 200\n']

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

Note:
In the first sample, the optimal order is: 10, 20, 30, 40, 50.

In the second sample, the optimal order is: 100, 200, 100, 200.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yura is tasked to build a closed fence in shape of an arbitrary non-degenerate simple quadrilateral. He's already got three straight fence segments with known lengths $a$, $b$, and $c$. Now he needs to find out some possible integer length $d$ of the fourth straight fence segment so that he can build the fence using these four segments. In other words, the fence should have a quadrilateral shape with side lengths equal to $a$, $b$, $c$, and $d$. Help Yura, find any possible length of the fourth side.

A non-degenerate simple quadrilateral is such a quadrilateral that no three of its corners lie on the same line, and it does not cross itself.


-----Input-----

The first line contains a single integer $t$ — the number of test cases ($1 \le t \le 1000$). The next $t$ lines describe the test cases.

Each line contains three integers $a$, $b$, and $c$ — the lengths of the three fence segments ($1 \le a, b, c \le 10^9$).


-----Output-----

For each test case print a single integer $d$ — the length of the fourth fence segment that is suitable for building the fence. If there are multiple answers, print any. We can show that an answer always exists.


-----Example-----
Input
2
1 2 3
12 34 56

Output
4
42



-----Note-----

We can build a quadrilateral with sides $1$, $2$, $3$, $4$.

We can build a quadrilateral with sides $12$, $34$, $56$, $42$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Edward Elric is chasing after Scar. To stop Edward, Scar creates $N$ barriers in the way, numbered from $1$ to $N$. 
Each barrier Scar created is either one of the following two types.
Type 1 barrier - This barrier starts from a height $X$ above the ground and extends till the sky.
Type 2 barrier - This barrier starts from the ground and extends up to height $X$ above the ground.

The height of Edward is $H$ units and he has an alchemic life force of $L$ units. Moreover, he can duck by $Y_{1}$ units and jump by height $Y_{2}$ units (as explained in the figures). He starts crossing barriers in sequence, starting from barrier $1$ till the barrier $N$. Whenever he can't pass a barrier by ducking or jumping (considered passed even when the barrier just touches him), he uses Alchemy to break the barrier. However, this costs him a single unit of his alchemic life force.

If after breaking a barrier no life force is left, Edward gets completely exhausted, unable to pass that barrier.   
How many barriers can Edward cross?   

And remember never to call him a pipsqueak if his height is too short!

------  Input: ------

The first line contains $T$, the number of test cases. Then the test cases follow. 
For each test case, the first line contains five integers $N$, $H$, $Y_{1}$, $Y_{2}$ and $L$.
The i-th of the next $N$ lines contains two integers $t_{i}$ and $X_{i}$ for the $i^{th}$ barrier where $t_{i} = 1$ denotes a Type 1 Barrier and $t_{i} = 2$ denotes a Type 2 barrier.
  
------  Output: ------
For each test case print a single line containing the number of barriers Edward can pass.
  
------  Constraints  ------
$1 ≤ T≤ 100$   
$1 ≤ N≤ 10^{3}$    
$2 ≤ H≤ 10^{3}$   
$1 ≤ Y_{1} < H$   
$1 ≤ Y_{2} ≤ 10^{3}$    
$1 ≤ L ≤ N$    
$1 ≤ t_{i} ≤ 2$
$1 ≤ X_{i}≤ 10^{3}$ 

----- Sample Input 1 ------ 
3
6 5 1 2 3
2 2
2 1
1 10
2 8
2 4
1 2
1 4 2 5 1
2 6
6 5 1 2 3
2 2
2 1
1 10
2 8
2 4
1 6
----- Sample Output 1 ------ 
5
0
6
----- explanation 1 ------ 
Test Case 1:    

Given $N = 6$, $H = 5$, $Y_{1} = 1$, $Y_{2} = 2$ and $L = 3$.    
He passes the first three barriers by either ducking or jumping. He uses alchemic life force for breaking $4^{th}$, $5^{th}$ and $6^{th}$ barriers because he cannot pass them by either jumping or ducking. He gets exhausted after breaking the $6^{th}$ barrier and is unable to pass it. So, in total he passes $5$ barriers.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
E869120 has A 1-yen coins and infinitely many 500-yen coins.

Determine if he can pay exactly N yen using only these coins.

-----Constraints-----
 - N is an integer between 1 and 10000 (inclusive).
 - A is an integer between 0 and 1000 (inclusive).

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

-----Output-----
If E869120 can pay exactly N yen using only his 1-yen and 500-yen coins, print Yes; otherwise, print No.

-----Sample Input-----
2018
218

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

We can pay 2018 yen with four 500-yen coins and 18 1-yen coins, so the answer is Yes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are 2N balls in the xy-plane. The coordinates of the i-th of them is (x_i, y_i).
Here, x_i and y_i are integers between 1 and N (inclusive) for all i, and no two balls occupy the same coordinates.
In order to collect these balls, Snuke prepared 2N robots, N of type A and N of type B.
Then, he placed the type-A robots at coordinates (1, 0), (2, 0), ..., (N, 0), and the type-B robots at coordinates (0, 1), (0, 2), ..., (0, N), one at each position.
When activated, each type of robot will operate as follows.
 - When a type-A robot is activated at coordinates (a, 0), it will move to the position of the ball with the lowest y-coordinate among the balls on the line x = a, collect the ball and deactivate itself. If there is no such ball, it will just deactivate itself without doing anything.
 - When a type-B robot is activated at coordinates (0, b), it will move to the position of the ball with the lowest x-coordinate among the balls on the line y = b, collect the ball and deactivate itself. If there is no such ball, it will just deactivate itself without doing anything.
Once deactivated, a robot cannot be activated again. Also, while a robot is operating, no new robot can be activated until the operating robot is deactivated.
When Snuke was about to activate a robot, he noticed that he may fail to collect all the balls, depending on the order of activating the robots.
Among the (2N)! possible orders of activating the robots, find the number of the ones such that all the balls can be collected, modulo 1 000 000 007.

-----Constraints-----
 - 2 \leq N \leq 10^5
 - 1 \leq x_i \leq N
 - 1 \leq y_i \leq N
 - If i ≠ j, either x_i ≠ x_j or y_i ≠ y_j.

-----Inputs-----
Input is given from Standard Input in the following format:
N
x_1 y_1
...
x_{2N} y_{2N}

-----Outputs-----
Print the number of the orders of activating the robots such that all the balls can be collected, modulo 1 000 000 007.

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

-----Sample Output-----
8

We will refer to the robots placed at (1, 0) and (2, 0) as A1 and A2, respectively, and the robots placed at (0, 1) and (0, 2) as B1 and B2, respectively.
There are eight orders of activation that satisfy the condition, as follows:
 - A1, B1, A2, B2
 - A1, B1, B2, A2
 - A1, B2, B1, A2
 - A2, B1, A1, B2
 - B1, A1, B2, A2
 - B1, A1, A2, B2
 - B1, A2, A1, B2
 - B2, A1, B1, A2
Thus, the output should be 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You and Fredrick are good friends. Yesterday, Fredrick received $N$ credit cards from ABCD Bank. He wants to verify whether his credit card numbers are valid or not. You happen to be great at regex so he is asking for your help!

A valid credit card from ABCD Bank has the following characteristics: 

► It must start with a $4$, $5$ or $6$. 

► It must contain exactly $\mbox{16}$ digits. 

► It must only consist of digits ($\mbox{0}$-$\mbox{9}$). 

► It may have digits in groups of $4$, separated by one hyphen "-". 

► It must NOT use any other separator like ' ' , '_', etc. 

► It must NOT have $4$ or more consecutive repeated digits.    

Examples:  

Valid Credit Card Numbers  

4253625879615786
4424424424442444
5122-2368-7954-3214

Invalid Credit Card Numbers  

42536258796157867       #17 digits in card number → Invalid 
4424444424442444        #Consecutive digits are repeating 4 or more times → Invalid
5122-2368-7954 - 3214   #Separators other than '-' are used → Invalid
44244x4424442444        #Contains non digit characters → Invalid
0525362587961578        #Doesn't start with 4, 5 or 6 → Invalid

Input Format

The first line of input contains an integer $N$. 

The next $N$ lines contain credit card numbers.  

Constraints  

$0<N<100$

Output Format

Print 'Valid' if the credit card number is valid. Otherwise, print 'Invalid'. Do not print the quotes.

Sample Input
6
4123456789123456
5123-4567-8912-3456
61234-567-8912-3456
4123356789123456
5133-3367-8912-3456
5123 - 3567 - 8912 - 3456

Sample Output
Valid
Valid
Invalid
Valid
Invalid
Invalid

Explanation

4123456789123456 : Valid 

5123-4567-8912-3456  : Valid 

61234-567-8912-3456  : Invalid, because the card number is not divided into equal groups of 4. 

4123356789123456  : Valid 

5133-3367-8912-3456  : Invalid, consecutive digits $3333$ is repeating 4 times. 

5123-4567-8912-3456 :  Invalid, because space '  ' and -  are used as separators.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp urgently needs a shovel! He comes to the shop and chooses an appropriate one. The shovel that Policarp chooses is sold for k burles. Assume that there is an unlimited number of such shovels in the shop.

In his pocket Polycarp has an unlimited number of "10-burle coins" and exactly one coin of r burles (1 ≤ r ≤ 9).

What is the minimum number of shovels Polycarp has to buy so that he can pay for the purchase without any change? It is obvious that he can pay for 10 shovels without any change (by paying the requied amount of 10-burle coins and not using the coin of r burles). But perhaps he can buy fewer shovels and pay without any change. Note that Polycarp should buy at least one shovel.


-----Input-----

The single line of input contains two integers k and r (1 ≤ k ≤ 1000, 1 ≤ r ≤ 9) — the price of one shovel and the denomination of the coin in Polycarp's pocket that is different from "10-burle coins". 

Remember that he has an unlimited number of coins in the denomination of 10, that is, Polycarp has enough money to buy any number of shovels.


-----Output-----

Print the required minimum number of shovels Polycarp has to buy so that he can pay for them without any change. 


-----Examples-----
Input
117 3

Output
9

Input
237 7

Output
1

Input
15 2

Output
2



-----Note-----

In the first example Polycarp can buy 9 shovels and pay 9·117 = 1053 burles. Indeed, he can pay this sum by using 10-burle coins and one 3-burle coin. He can't buy fewer shovels without any change.

In the second example it is enough for Polycarp to buy one shovel.

In the third example Polycarp should buy two shovels and pay 2·15 = 30 burles. It is obvious that he can pay this sum without any change.

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