vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
It's that time of the year, Felicity is around the corner and you can see people celebrating all around the Himalayan region. The Himalayan region has n gyms. The i-th gym has g_{i} Pokemon in it. There are m distinct Pokemon types in the Himalayan region numbered from 1 to m. There is a special evolution camp set up in the fest which claims to evolve any Pokemon. The type of a Pokemon could change after evolving, subject to the constraint that if two Pokemon have the same type before evolving, they will have the same type after evolving. Also, if two Pokemon have different types before evolving, they will have different types after evolving. It is also possible that a Pokemon has the same type before and after evolving. 

Formally, an evolution plan is a permutation f of {1, 2, ..., m}, such that f(x) = y means that a Pokemon of type x evolves into a Pokemon of type y.

The gym leaders are intrigued by the special evolution camp and all of them plan to evolve their Pokemons. The protocol of the mountain states that in each gym, for every type of Pokemon, the number of Pokemon of that type before evolving any Pokemon should be equal the number of Pokemon of that type after evolving all the Pokemons according to the evolution plan. They now want to find out how many distinct evolution plans exist which satisfy the protocol.

Two evolution plans f_1 and f_2 are distinct, if they have at least one Pokemon type evolving into a different Pokemon type in the two plans, i. e. there exists an i such that f_1(i) ≠ f_2(i).

Your task is to find how many distinct evolution plans are possible such that if all Pokemon in all the gyms are evolved, the number of Pokemon of each type in each of the gyms remains the same. As the answer can be large, output it modulo 10^9 + 7.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^6) — the number of gyms and the number of Pokemon types.

The next n lines contain the description of Pokemons in the gyms. The i-th of these lines begins with the integer g_{i} (1 ≤ g_{i} ≤ 10^5) — the number of Pokemon in the i-th gym. After that g_{i} integers follow, denoting types of the Pokemons in the i-th gym. Each of these integers is between 1 and m.

The total number of Pokemons (the sum of all g_{i}) does not exceed 5·10^5.


-----Output-----

Output the number of valid evolution plans modulo 10^9 + 7.


-----Examples-----
Input
2 3
2 1 2
2 2 3

Output
1

Input
1 3
3 1 2 3

Output
6

Input
2 4
2 1 2
3 2 3 4

Output
2

Input
2 2
3 2 2 1
2 1 2

Output
1

Input
3 7
2 1 2
2 3 4
3 5 6 7

Output
24



-----Note-----

In the first case, the only possible evolution plan is: $1 \rightarrow 1,2 \rightarrow 2,3 \rightarrow 3$

In the second case, any permutation of (1,  2,  3) is valid.

In the third case, there are two possible plans: $1 \rightarrow 1,2 \rightarrow 2,3 \rightarrow 4,4 \rightarrow 3$ $1 \rightarrow 1,2 \rightarrow 2,3 \rightarrow 3,4 \rightarrow 4$

In the fourth case, the only possible evolution plan is: $1 \rightarrow 1,2 \rightarrow 2$

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Genos recently installed the game Zuma on his phone. In Zuma there exists a line of *n* gemstones, the *i*-th of which has color *c**i*. The goal of the game is to destroy all the gemstones in the line as quickly as possible.

In one second, Genos is able to choose exactly one continuous substring of colored gemstones that is a palindrome and remove it from the line. After the substring is removed, the remaining gemstones shift to form a solid line again. What is the minimum number of seconds needed to destroy the entire line?

Let us remind, that the string (or substring) is called palindrome, if it reads same backwards or forward. In our case this means the color of the first gemstone is equal to the color of the last one, the color of the second gemstone is equal to the color of the next to last and so on.

Input Specification:
The first line of input contains a single integer *n* (1<=≤<=*n*<=≤<=500) — the number of gemstones.

The second line contains *n* space-separated integers, the *i*-th of which is *c**i* (1<=≤<=*c**i*<=≤<=*n*) — the color of the *i*-th gemstone in a line.

Output Specification:
Print a single integer — the minimum number of seconds needed to destroy the entire line.

Demo Input:
['3\n1 2 1\n', '3\n1 2 3\n', '7\n1 4 4 2 3 2 1\n']

Demo Output:
['1\n', '3\n', '2\n']

Note:
In the first sample, Genos can destroy the entire line in one second.

In the second sample, Genos can only destroy one gemstone at a time, so destroying three gemstones takes three seconds.

In the third sample, to achieve the optimal time of two seconds, destroy palindrome 4 4 first and then destroy palindrome 1 2 3 2 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Game of chess unfinished

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Once Volodya was at the museum and saw a regular chessboard as a museum piece. And there were only four chess pieces on it: two white rooks, a white king and a black king. "Aha, blacks certainly didn't win!", — Volodya said and was right for sure. And your task is to say whether whites had won or not.

Pieces on the chessboard are guaranteed to represent a correct position (every piece occupies one cell, no two pieces occupy the same cell and kings cannot take each other). Thus, your task is only to decide whether whites mate blacks. We would remind you that it means that the black king can be taken by one of the opponent's pieces at the moment and also it cannot move to an unbeaten position. A rook moves vertically or horizontally by any number of free cells (assuming there are no other pieces on its path), a king — to the adjacent cells (either by corner or by side). Certainly, pieces cannot leave the board. The black king might be able to take opponent's rooks at his turn (see sample 3).

Input Specification:
The input contains 4 space-separated piece positions: positions of the two rooks, the white king and the black king. Each position on 8<=×<=8 chessboard is denoted by two symbols — ('a' - 'h') and ('1' - '8') — which stand for horizontal and vertical coordinates of the cell occupied by the piece. It is guaranteed, that no two pieces occupy the same cell, and kings cannot take each other.

Output Specification:
Output should contain one word: "CHECKMATE" if whites mate blacks, and "OTHER" otherwise.

Demo Input:
['a6 b4 c8 a8\n', 'a6 c4 b6 b8\n', 'a2 b1 a3 a1\n']

Demo Output:
['CHECKMATE\n', 'OTHER\n', 'OTHER\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Sereja has a bracket sequence *s*1,<=*s*2,<=...,<=*s**n*, or, in other words, a string *s* of length *n*, consisting of characters "(" and ")".

Sereja needs to answer *m* queries, each of them is described by two integers *l**i*,<=*r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*). The answer to the *i*-th query is the length of the maximum correct bracket subsequence of sequence *s**l**i*,<=*s**l**i*<=+<=1,<=...,<=*s**r**i*. Help Sereja answer all queries.

You can find the definitions for a subsequence and a correct bracket sequence in the notes.

Input Specification:
The first line contains a sequence of characters *s*1,<=*s*2,<=...,<=*s**n* (1<=≤<=*n*<=≤<=106) without any spaces. Each character is either a "(" or a ")". The second line contains integer *m* (1<=≤<=*m*<=≤<=105) — the number of queries. Each of the next *m* lines contains a pair of integers. The *i*-th line contains integers *l**i*,<=*r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*) — the description of the *i*-th query.

Output Specification:
Print the answer to each question on a single line. Print the answers in the order they go in the input.

Demo Input:
['())(())(())(\n7\n1 1\n2 3\n1 2\n1 12\n8 12\n5 11\n2 10\n']

Demo Output:
['0\n0\n2\n10\n4\n6\n6\n']

Note:
A subsequence of length |*x*| of string *s* = *s*<sub class="lower-index">1</sub>*s*<sub class="lower-index">2</sub>... *s*<sub class="lower-index">|*s*|</sub> (where |*s*| is the length of string *s*) is string *x* = *s*<sub class="lower-index">*k*<sub class="lower-index">1</sub></sub>*s*<sub class="lower-index">*k*<sub class="lower-index">2</sub></sub>... *s*<sub class="lower-index">*k*<sub class="lower-index">|*x*|</sub></sub> (1 ≤ *k*<sub class="lower-index">1</sub> &lt; *k*<sub class="lower-index">2</sub> &lt; ... &lt; *k*<sub class="lower-index">|*x*|</sub> ≤ |*s*|).

A correct bracket sequence is a bracket sequence that can be transformed into a correct aryphmetic expression by inserting characters "1" and "+" between the characters of the string. For example, bracket sequences "()()", "(())" are correct (the resulting expressions "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

For the third query required sequence will be «()».

For the fourth query required sequence will be «()(())(())».

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are two sequences A and B, both of length N. A and B are each sorted in the ascending order. Check if it is possible to reorder the terms of B so that for each i (1 \leq i \leq N) A_i \neq B_i holds, and if it is possible, output any of the reorderings that achieve it.

Constraints

* 1\leq N \leq 2 \times 10^5
* 1\leq A_i,B_i \leq N
* A and B are each sorted in the ascending order.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N


Output

If there exist no reorderings that satisfy the condition, print `No`.

If there exists a reordering that satisfies the condition, print `Yes` on the first line. After that, print a reordering of B on the second line, separating terms with a whitespace.

If there are multiple reorderings that satisfy the condition, you can print any of them.

Examples

Input

6
1 1 1 2 2 3
1 1 1 2 2 3


Output

Yes
2 2 3 1 1 1


Input

3
1 1 2
1 1 3


Output

No


Input

4
1 1 2 3
1 2 3 3


Output

Yes
3 3 1 2

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
SaMer has written the greatest test case of all time for one of his problems. For a given array of integers, the problem asks to find the minimum number of groups the array can be divided into, such that the product of any pair of integers in the same group is a perfect square. 

Each integer must be in exactly one group. However, integers in a group do not necessarily have to be contiguous in the array.

SaMer wishes to create more cases from the test case he already has. His test case has an array $A$ of $n$ integers, and he needs to find the number of contiguous subarrays of $A$ that have an answer to the problem equal to $k$ for each integer $k$ between $1$ and $n$ (inclusive).

Input Specification:
The first line of input contains a single integer $n$ ($1 \leq n \leq 5000$), the size of the array.

The second line contains $n$ integers $a_1$,$a_2$,$\dots$,$a_n$ ($-10^8 \leq a_i \leq 10^8$), the values of the array.

Output Specification:
Output $n$ space-separated integers, the $k$-th integer should be the number of contiguous subarrays of $A$ that have an answer to the problem equal to $k$.

Demo Input:
['2\n5 5\n', '5\n5 -4 2 1 8\n', '1\n0\n']

Demo Output:
['3 0\n', '5 5 3 2 0\n', '1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arthur has bought a beautiful big table into his new flat. When he came home, Arthur noticed that the new table is unstable.

In total the table Arthur bought has n legs, the length of the i-th leg is l_{i}.

Arthur decided to make the table stable and remove some legs. For each of them Arthur determined number d_{i} — the amount of energy that he spends to remove the i-th leg.

A table with k legs is assumed to be stable if there are more than half legs of the maximum length. For example, to make a table with 5 legs stable, you need to make sure it has at least three (out of these five) legs of the maximum length. Also, a table with one leg is always stable and a table with two legs is stable if and only if they have the same lengths.

Your task is to help Arthur and count the minimum number of energy units Arthur should spend on making the table stable.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 10^5) — the initial number of legs in the table Arthur bought.

The second line of the input contains a sequence of n integers l_{i} (1 ≤ l_{i} ≤ 10^5), where l_{i} is equal to the length of the i-th leg of the table.

The third line of the input contains a sequence of n integers d_{i} (1 ≤ d_{i} ≤ 200), where d_{i} is the number of energy units that Arthur spends on removing the i-th leg off the table.


-----Output-----

Print a single integer — the minimum number of energy units that Arthur needs to spend in order to make the table stable.


-----Examples-----
Input
2
1 5
3 2

Output
2

Input
3
2 4 4
1 1 1

Output
0

Input
6
2 2 1 1 3 3
4 3 5 5 2 1

Output
8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The big café chain Espresso Bucks is expanding to the country of Gridland. Since you are an expert on Gridland culture and geography, Espresso Bucks have hired you to decide where to put their coffee shops for maximum profit. Gridland consists of an $n$ by $m$ grid, where some cells are land, and some are water. At most one coffee shop can be built on each land cell. Nothing can be built on the water cells, but on the other hand, no one lives in the water. After a lot of long meetings with the Espresso Bucks people, you have come to the conclusion that there are only two constraints the placement of coffee shops has to satisfy: 
 - Each land cell must have a coffee shop directly on it, or adjacent to it.
 - No two coffee shops can be adjacent to each other.

Two cells are adjacent if one is immediately to the west, north, east, or south of the other. Find any placement of coffee shops that satisfies these constraints.

-----Input-----
The first line of input consists of two integers $n$ and $m$ ($1 \leq n,m \leq 100$). The following $n$ lines each contain a string of length $m$ consisting only of the characters ‘.’ (land) and ‘#’ (water). This is the map of gridland. It is guaranteed that the map contains at least one land cell.

-----Output-----
Output a copy of the map of gridland, where some of the land cells have been replaced with the letter ‘E’, meaning that a coffee shop was placed on the corresponding land cell. This placement should satisfy the constraints above. If there are many solutions, any one will be accepted.

-----Examples-----
Sample Input:
5 6
....#.
....#.
#.....
......
##...#
Sample Output:
E..E#.
..E.#E
#..E..
.E...E
##E.E#

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The police department of your city has just started its journey. Initially, they don’t have any manpower. So, they started hiring new recruits in groups.

Meanwhile, crimes keeps occurring within the city. One member of the police force can investigate only one crime during his/her lifetime.

If there is no police officer free (isn't busy with crime) during the occurrence of a crime, it will go untreated.

Given the chronological order of crime occurrences and recruit hirings, find the number of crimes which will go untreated.

Input Specification:
The first line of input will contain an integer *n* (1<=≤<=*n*<=≤<=105), the number of events. The next line will contain *n* space-separated integers.

If the integer is -1 then it means a crime has occurred. Otherwise, the integer will be positive, the number of officers recruited together at that time. No more than 10 officers will be recruited at a time.

Output Specification:
Print a single integer, the number of crimes which will go untreated.

Demo Input:
['3\n-1 -1 1\n', '8\n1 -1 1 -1 -1 1 1 1\n', '11\n-1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\n']

Demo Output:
['2\n', '1\n', '8\n']

Note:
Lets consider the second example:
 1.  Firstly one person is hired. 1.  Then crime appears, the last hired person will investigate this crime. 1.  One more person is hired. 1.  One more crime appears, the last hired person will investigate this crime. 1.  Crime appears. There is no free policeman at the time, so this crime will go untreated. 1.  One more person is hired. 1.  One more person is hired. 1.  One more person is hired. 
The answer is one, as one crime (on step 5) will go untreated.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A string is called happy if it does not have any of the strings 'aaa', 'bbb' or 'ccc' as a substring.
Given three integers a, b and c, return any string s, which satisfies following conditions:

s is happy and longest possible.
s contains at most a occurrences of the letter 'a', at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.
s will only contain 'a', 'b' and 'c' letters.

If there is no such string s return the empty string "".
 
Example 1:
Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:
Input: a = 2, b = 2, c = 1
Output: "aabbc"

Example 3:
Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It's the only correct answer in this case.

 
Constraints:

0 <= a, b, c <= 100
a + b + c > 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Valera and Antique Items

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valera is a collector. Once he wanted to expand his collection with exactly one antique item.

Valera knows *n* sellers of antiques, the *i*-th of them auctioned *k**i* items. Currently the auction price of the *j*-th object of the *i*-th seller is *s**ij*. Valera gets on well with each of the *n* sellers. He is perfectly sure that if he outbids the current price of one of the items in the auction (in other words, offers the seller the money that is strictly greater than the current price of the item at the auction), the seller of the object will immediately sign a contract with him.

Unfortunately, Valera has only *v* units of money. Help him to determine which of the *n* sellers he can make a deal with.

Input Specification:
The first line contains two space-separated integers *n*,<=*v* (1<=≤<=*n*<=≤<=50; 104<=≤<=*v*<=≤<=106) — the number of sellers and the units of money the Valera has.

Then *n* lines follow. The *i*-th line first contains integer *k**i* (1<=≤<=*k**i*<=≤<=50) the number of items of the *i*-th seller. Then go *k**i* space-separated integers *s**i*1,<=*s**i*2,<=...,<=*s**ik**i* (104<=≤<=*s**ij*<=≤<=106) — the current prices of the items of the *i*-th seller.

Output Specification:
In the first line, print integer *p* — the number of sellers with who Valera can make a deal.

In the second line print *p* space-separated integers *q*1,<=*q*2,<=...,<=*q**p* (1<=≤<=*q**i*<=≤<=*n*) — the numbers of the sellers with who Valera can make a deal. Print the numbers of the sellers in the increasing order.

Demo Input:
['3 50000\n1 40000\n2 20000 60000\n3 10000 70000 190000\n', '3 50000\n1 50000\n3 100000 120000 110000\n3 120000 110000 120000\n']

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

Note:
In the first sample Valera can bargain with each of the sellers. He can outbid the following items: a 40000 item from the first seller, a 20000 item from the second seller, and a 10000 item from the third seller.

In the second sample Valera can not make a deal with any of the sellers, as the prices of all items in the auction too big for him.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After Misha's birthday he had many large numbers left, scattered across the room. Now it's time to clean up and Misha needs to put them in a basket. He ordered this task to his pet robot that agreed to complete the task at certain conditions. Before the robot puts a number x to the basket, Misha should answer the question: is it possible to choose one or multiple numbers that already are in the basket, such that their XOR sum equals x? 

If the answer is positive, you also need to give the indexes of these numbers. If there are multiple options of choosing numbers, you are allowed to choose any correct option. After Misha's answer the robot puts the number to the basket.

Initially the basket is empty. Each integer you put in the basket takes some number. The first integer you put into the basket take number 0, the second integer takes number 1 and so on.

Misha needs to clean up the place as soon as possible but unfortunately, he isn't that good at mathematics. He asks you to help him.


-----Input-----

The first line contains number m (1 ≤ m ≤ 2000), showing how many numbers are scattered around the room.

The next m lines contain the numbers in the order in which the robot puts them in the basket. Each number is a positive integer strictly less than 10^600 that doesn't contain leading zeroes. 


-----Output-----

For each number either print a 0 on the corresponding line, if the number cannot be represented as a XOR sum of numbers that are in the basket, or print integer k showing how many numbers are in the representation and the indexes of these numbers. Separate the numbers by spaces. Each number can occur in the representation at most once.


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

Output
0
0
0
3 0 1 2
2 1 2
2 0 2
2 0 1

Input
2
5
5

Output
0
1 0



-----Note-----

The XOR sum of numbers is the result of bitwise sum of numbers modulo 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence a consisting of n integers. You may partition this sequence into two sequences b and c in such a way that every element belongs exactly to one of these sequences. 

Let B be the sum of elements belonging to b, and C be the sum of elements belonging to c (if some of these sequences is empty, then its sum is 0). What is the maximum possible value of B - C?


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 100) — the number of elements in a.

The second line contains n integers a_1, a_2, ..., a_{n} ( - 100 ≤ a_{i} ≤ 100) — the elements of sequence a.


-----Output-----

Print the maximum possible value of B - C, where B is the sum of elements of sequence b, and C is the sum of elements of sequence c.


-----Examples-----
Input
3
1 -2 0

Output
3

Input
6
16 23 16 15 42 8

Output
120



-----Note-----

In the first example we may choose b = {1, 0}, c = { - 2}. Then B = 1, C =  - 2, B - C = 3.

In the second example we choose b = {16, 23, 16, 15, 42, 8}, c = {} (an empty sequence). Then B = 120, C = 0, B - C = 120.

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