vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are the organizer of the famous "Zurich Music Festival". There will be n singers who will perform at the festival, identified by the integers 1, 2, ..., n. You must choose in which order they are going to perform on stage. 

You have m friends and each of them has a set of favourite singers. More precisely, for each 1≤ i≤ m, the i-th friend likes singers s_{i,1},   s_{i, 2},   ..., \,s_{i, q_i}.

A friend of yours is happy if the singers he likes perform consecutively (in an arbitrary order). An ordering of the singers is valid if it makes all your friends happy.

Compute the number of valid orderings modulo 998 244 353.

Input

The first line contains two integers n and m (1≤ n,\,m≤ 100) — the number of singers and the number of friends correspondingly.

The i-th of the next m lines contains the integer q_i (1≤ q_i≤ n) — the number of favorite singers of the i-th friend – followed by the q_i integers s_{i,1},   s_{i, 2},   ..., \,s_{i, q_i} (1≤ s_{i,1}<s_{i,2}<⋅⋅⋅<s_{i,q_i}≤ n) — the indexes of his favorite singers.

Output

Print the number of valid orderings of the singers modulo 998 244 353.

Examples

Input


3 1
2 1 3


Output


4


Input


5 5
2 1 2
2 2 3
2 3 4
2 4 5
2 1 5


Output


0


Input


100 1
1 50


Output


35305197


Input


5 1
5 1 2 3 4 5


Output


120


Input


2 5
1 2
1 2
1 2
1 1
1 1


Output


2


Input


11 4
5 4 5 7 9 11
2 2 10
2 9 11
7 1 2 3 5 8 10 11


Output


384

Note

Explanation of the first sample: There are 3 singers and only 1 friend. The friend likes the two singers 1 and 3. Thus, the 4 valid orderings are: 

  * 1 3 2
  * 2 1 3
  * 2 3 1
  * 3 1 2



Explanation of the second sample: There are 5 singers and 5 friends. One can show that no ordering is valid.

Explanation of the third sample: There are 100 singers and only 1 friend. The friend likes only singer 50, hence all the 100! possible orderings are valid.

Explanation of the fourth sample: There are 5 singers and only 1 friend. The friend likes all the singers, hence all the 5!=120 possible orderings are valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Deoxyribonucleic acid (DNA) is a chemical found in the nucleus of cells and carries the "instructions" for the development and functioning of living organisms.

If you want to know more http://en.wikipedia.org/wiki/DNA

In DNA strings, symbols "A" and "T" are complements of each other, as "C" and "G". 
You have function with one side of the DNA (string, except for Haskell); you need to get the other complementary side. DNA strand is never empty or there is no DNA at all (again, except for Haskell).

More similar exercise are found here http://rosalind.info/problems/list-view/ (source)

```python
DNA_strand ("ATTGC") # return "TAACG"

DNA_strand ("GTAT") # return "CATA"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today Omar has assignment problems from his math professor. Yes, Omar has infinite number of questions that he must solve today. The first problem went something like this.  

Given N integers in the form of A_i where 1 ≤ i ≤ N, Omar wants to make each number A_i in the N numbers equal to M. To convert a number A_i to M, it will cost |M - A_i| units. The problem asks to find out the minimum cost to convert all the N numbers to M, so you should choose the best M to get the minimum cost. 

Omar gets bored easily from these kind of questions, can you solve it for him ?

Input:

First line of the input contains an integer T denoting the number of test cases. 
First line of every test-case contains an integer N.      
Second line of every test case contains N space separated integers A_i.

Output:

For each case, print the minimum cost that Omar needs to pay to convert each A_i to M, in a separate line.   

Constraints:

1 ≤ T ≤ 10.
1 ≤ N ≤ 10 ^ 5.
1 ≤ A_i ≤ 10^{9}

SAMPLE INPUT
1
4
1 2 4 5

SAMPLE OUTPUT
6

Explanation

One of the best M's you could choose in this case is 3.   
So the answer = |1 - 3| + |2 - 3| + |4 - 3| + |5 - 3| = 6.

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

Taro hides important books in the school locker, so he manages them more strictly than other people, and in addition to the keys provided by the school, he has installed the following button authentication type keys. ..

<image>

However, Taro, who easily forgets his password, has a habit of making it possible to write his password in one stroke. Even more sweet Taro wrote the candidates on paper when he thought about his password. Jiro, who happened to pick up the paper, tried to open the locker without throwing it away because he had a bad personality.

However, there are as many as 1000 password proposals written on the paper, and it seems that the sun will go down if you try all the inputs. Therefore, Jiro, who knows Taro's habits, decided to pick up only the ones that can be written with one stroke from the 1000 passwords in order to reduce the number of examinations, and asked the programmer to do the work.

There is always one or more candidates for each dataset. The rules for one-stroke writing are shown below.

1. The same characters are not consecutive. For example, AAA is not allowed.
2. One-stroke writing is possible in four directions, up, down, left and right. Do not move diagonally.
3. It does not go out of the frame of the button array and continue. Movement such as ABCA is not allowed.
4. You can pass over the characters that you have passed once.
5. Input of only one character of the button is regarded as one-stroke writing.



Input

The input consists of a group of 1000 character strings as shown below, and each line is an uppercase alphabetic string of 1 to 10 characters from A to I. It is assumed that there is no duplication of character string data.


string1
string2
...
string1000


Output

Extract only the candidate passwords (candidatePassword) from the input and list them as follows. In the following cases, N candidates are listed.


candidatePassword1
candidatePassword2
...
candidatePasswordN


The output is the same as the order of the input strings and the order must not be changed.

Example

Input

ABCFI
ABCABCABC
AEI
EFC
（中略）
DEHED
EEEEE
（以上でちょうど1000個）


Output

ABCFI
EFC
（中略）
DEHED

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Recently Ivan noticed an array *a* while debugging his code. Now Ivan can't remember this array, but the bug he was trying to fix didn't go away, so Ivan thinks that the data from this array might help him to reproduce the bug.

Ivan clearly remembers that there were *n* elements in the array, and each element was not less than 1 and not greater than *n*. Also he remembers *q* facts about the array. There are two types of facts that Ivan remembers:
 -  1 *l**i* *r**i* *v**i* — for each *x* such that *l**i*<=≤<=*x*<=≤<=*r**i* *a**x*<=≥<=*v**i*; -  2 *l**i* *r**i* *v**i* — for each *x* such that *l**i*<=≤<=*x*<=≤<=*r**i* *a**x*<=≤<=*v**i*. 
Also Ivan thinks that this array was a permutation, but he is not so sure about it. He wants to restore some array that corresponds to the *q* facts that he remembers and is very similar to permutation. Formally, Ivan has denoted the *cost* of array as follows:

, where *cnt*(*i*) is the number of occurences of *i* in the array.

Help Ivan to determine minimum possible *cost* of the array that corresponds to the facts!

Input Specification:
The first line contains two integer numbers *n* and *q* (1<=≤<=*n*<=≤<=50, 0<=≤<=*q*<=≤<=100).

Then *q* lines follow, each representing a fact about the array. *i*-th line contains the numbers *t**i*, *l**i*, *r**i* and *v**i* for *i*-th fact (1<=≤<=*t**i*<=≤<=2, 1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*, 1<=≤<=*v**i*<=≤<=*n*, *t**i* denotes the type of the fact).

Output Specification:
If the facts are controversial and there is no array that corresponds to them, print -1. Otherwise, print minimum possible *cost* of the array.

Demo Input:
['3 0\n', '3 1\n1 1 3 2\n', '3 2\n1 1 3 2\n2 1 3 2\n', '3 2\n1 1 3 2\n2 1 3 1\n']

Demo Output:
['3\n', '5\n', '9\n', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a 2D rectangular grid. Each grid cell contains either an apple, an obstacle, or is empty. Empty cells are denoted as ’.’, apples as ’a’, and obstacles as ’#’. You are to implement a simulation of gravity, based on the following rules: 
 - The obstacles do not move.
 - Whenever there is an empty cell immediately below an apple, the apple moves into the empty cell.

Print out the final configuration of the board after all apples reach their final locations. Merely iterating the gravity rule, a step at a time, will likely take too long on large datasets.

-----Input-----
The input begins with a line containing integers $R$ and $C$, designating the number of rows and columns of the grid, such that $1 \leq R \leq 50000$ and $1 \leq C \leq 10$. The first line is followed by $R$ additional lines, each designating a row of the grid, from top to bottom. Each line has $C$ characters, each of which is either ’.’, ’a’, or ’#’.

-----Output-----
Output $R$ grid lines displaying the final state.

-----Examples-----
Sample Input:
3 3
aaa
#..
..#
Sample Output:
a..
#.a
.a#

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
All our characters have hobbies. The same is true for Fedor. He enjoys shopping in the neighboring supermarket. 

The goods in the supermarket have unique integer ids. Also, for every integer there is a product with id equal to this integer. Fedor has *n* discount coupons, the *i*-th of them can be used with products with ids ranging from *l**i* to *r**i*, inclusive. Today Fedor wants to take exactly *k* coupons with him.

Fedor wants to choose the *k* coupons in such a way that the number of such products *x* that all coupons can be used with this product *x* is as large as possible (for better understanding, see examples). Fedor wants to save his time as well, so he asks you to choose coupons for him. Help Fedor!

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=3·105) — the number of coupons Fedor has, and the number of coupons he wants to choose.

Each of the next *n* lines contains two integers *l**i* and *r**i* (<=-<=109<=≤<=*l**i*<=≤<=*r**i*<=≤<=109) — the description of the *i*-th coupon. The coupons can be equal.

Output Specification:
In the first line print single integer — the maximum number of products with which all the chosen coupons can be used. The products with which at least one coupon cannot be used shouldn't be counted.

In the second line print *k* distinct integers *p*1,<=*p*2,<=...,<=*p**k* (1<=≤<=*p**i*<=≤<=*n*) — the ids of the coupons which Fedor should choose.

If there are multiple answers, print any of them.

Demo Input:
['4 2\n1 100\n40 70\n120 130\n125 180\n', '3 2\n1 12\n15 20\n25 30\n', '5 2\n1 10\n5 15\n14 50\n30 70\n99 100\n']

Demo Output:
['31\n1 2 \n', '0\n1 2 \n', '21\n3 4 \n']

Note:
In the first example if we take the first two coupons then all the products with ids in range [40, 70] can be bought with both coupons. There are 31 products in total.

In the second example, no product can be bought with two coupons, that is why the answer is 0. Fedor can choose any two coupons in this example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given positive integers $N$ and $D$. You may perform operations of the following two types:
- add $D$ to $N$, i.e. change $N$ to $N+D$
- change $N$ to $\mathop{\mathrm{digitsum}}(N)$
Here, $\mathop{\mathrm{digitsum}}(x)$ is the sum of decimal digits of $x$. For example, $\mathop{\mathrm{digitsum}}(123)=1+2+3=6$, $\mathop{\mathrm{digitsum}}(100)=1+0+0=1$, $\mathop{\mathrm{digitsum}}(365)=3+6+5=14$.
You may perform any number of operations (including zero) in any order. Please find the minimum obtainable value of $N$ and the minimum number of operations required to obtain this value.

-----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 test case contains two space-separated integers $N$ and $D$.

-----Output-----
For each test case, print a single line containing two space-separated integers — the minimum value of $N$ and the minimum required number of operations.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N, D \le 10^{10}$

-----Subtasks-----
Subtask #1 (30 points): $1 \le N, D \le 100$
Subtask #2 (70 points): original constraints

-----Example Input-----
3
2 1
9 3
11 13

-----Example Output-----
1 9
3 2
1 4

-----Explanation-----
Example case 1: The value $N=1$ can be achieved by 8 successive "add" operations (changing $N$ to $10$) and one "digit-sum" operation.
Example case 2: You can prove that you cannot obtain $N=1$ and $N=2$, and you can obtain $N=3$.
The value $N=3$ can be achieved by one "add" and one "digitsum" operation, changing $9$ to $12$ and $12$ to $3$.  
Example case 3: $N=1$ can be achieved by operations "add", "add", "digitsum", "digitsum": $11 \rightarrow 24 \rightarrow 37 \rightarrow 10 \rightarrow 1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The online retailer Amagoogsoftbook currently offers $N$ different so-called “home assistants”, which it wants to recommend to its customers. For this recommendation, they wish to rank all the assistants. The quality of this ranking is not very important – multiple assistants may even be assigned the same rank – but they wish to maximize the number of distinct ranks assigned, to lessen the decision fatigue of their customers.

To ensure that the ranking is not completely arbitrary, they have collected for each assistant $i$ two measurements $a_ i$ and $b_ i$ – the quality of the jokes the assistant can tell and how nice are the compliments the assistant is able to give (clearly these are the two most important aspects). These measurements are of course somewhat subjective, so we wish to ignore small differences in them. However, if for two given assistants $i$ and $j$ we have that $a_ i + K < a_ j$ or $b_ i + K < b_ j$, the ranking of assistant $j$ must be the same or higher than the ranking of assistant $i$. This rule may force two products to be given the same ranking, for example if an assistant $i$ gives much better puns than assistant $j$, while assistant $j$ gives the superior self-esteem boosts.

What is the maximum number of distinct ranks, taken over all possible rankings?

-----Input-----
The first line contains the integers $1 \le N \le 100000$ and $0 \le K \le 10^9$ – the number of assistants and the measurement difference limit as described in the statement. The next line contains the $N$ integers $a_1, a_2, \dots , a_ N$. The next line contains the $N$ integers $b_1, b_2, \dots , b_ N$.

All measurements are between $0$ and $10^9$.

-----Output-----
Output a single integer: the maximum number of distinct ranks.

-----Examples-----
Sample Input 1:
2 10
1 12
1 13
Sample Output 1:
2

Sample Input 2:
2 10
1 5
1 12
Sample Output 2:
2

Sample Input 3:
2 10
1 5
1 4
Sample Output 3:
2

Sample Input 4:
2 10
1 5
4 1
Sample Output 4:
2

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
It is winter now, and Max decided it's about time he watered the garden.

The garden can be represented as *n* consecutive garden beds, numbered from 1 to *n*. *k* beds contain water taps (*i*-th tap is located in the bed *x**i*), which, if turned on, start delivering water to neighbouring beds. If the tap on the bed *x**i* is turned on, then after one second has passed, the bed *x**i* will be watered; after two seconds have passed, the beds from the segment [*x**i*<=-<=1,<=*x**i*<=+<=1] will be watered (if they exist); after *j* seconds have passed (*j* is an integer number), the beds from the segment [*x**i*<=-<=(*j*<=-<=1),<=*x**i*<=+<=(*j*<=-<=1)] will be watered (if they exist). Nothing changes during the seconds, so, for example, we can't say that the segment [*x**i*<=-<=2.5,<=*x**i*<=+<=2.5] will be watered after 2.5 seconds have passed; only the segment [*x**i*<=-<=2,<=*x**i*<=+<=2] will be watered at that moment.

Max wants to turn on all the water taps at the same moment, and now he wonders, what is the minimum number of seconds that have to pass after he turns on some taps until the whole garden is watered. Help him to find the answer!

Input Specification:
The first line contains one integer *t* — the number of test cases to solve (1<=≤<=*t*<=≤<=200).

Then *t* test cases follow. The first line of each test case contains two integers *n* and *k* (1<=≤<=*n*<=≤<=200, 1<=≤<=*k*<=≤<=*n*) — the number of garden beds and water taps, respectively.

Next line contains *k* integers *x**i* (1<=≤<=*x**i*<=≤<=*n*) — the location of *i*-th water tap. It is guaranteed that for each  condition *x**i*<=-<=1<=&lt;<=*x**i* holds.

It is guaranteed that the sum of *n* over all test cases doesn't exceed 200.

Note that in hacks you have to set *t*<==<=1.

Output Specification:
For each test case print one integer — the minimum number of seconds that have to pass after Max turns on some of the water taps, until the whole garden is watered.

Demo Input:
['3\n5 1\n3\n3 3\n1 2 3\n4 1\n1\n']

Demo Output:
['3\n1\n4\n']

Note:
The first example consists of 3 tests:
 1.  There are 5 garden beds, and a water tap in the bed 3. If we turn it on, then after 1 second passes, only bed 3 will be watered; after 2 seconds pass, beds [1, 3] will be watered, and after 3 seconds pass, everything will be watered. 1.  There are 3 garden beds, and there is a water tap in each one. If we turn all of them on, then everything will be watered after 1 second passes. 1.  There are 4 garden beds, and only one tap in the bed 1. It will take 4 seconds to water, for example, bed 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem differs from one which was on the online contest.

The sequence a1, a2, ..., an is called increasing, if ai < ai + 1 for i < n.

The sequence s1, s2, ..., sk is called the subsequence of the sequence a1, a2, ..., an, if there exist such a set of indexes 1 ≤ i1 < i2 < ... < ik ≤ n that aij = sj. In other words, the sequence s can be derived from the sequence a by crossing out some elements.

You are given two sequences of integer numbers. You are to find their longest common increasing subsequence, i.e. an increasing sequence of maximum length that is the subsequence of both sequences.

Input

The first line contains an integer n (1 ≤ n ≤ 500) — the length of the first sequence. The second line contains n space-separated integers from the range [0, 109] — elements of the first sequence. The third line contains an integer m (1 ≤ m ≤ 500) — the length of the second sequence. The fourth line contains m space-separated integers from the range [0, 109] — elements of the second sequence.

Output

In the first line output k — the length of the longest common increasing subsequence. In the second line output the subsequence itself. Separate the elements with a space. If there are several solutions, output any.

Examples

Input

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


Output

3
3 5 6 


Input

5
1 2 0 2 1
3
1 0 1


Output

2
0 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
To give credit where credit is due: This problem was taken from the ACMICPC-Northwest Regional Programming Contest. Thank you problem writers.

You are helping an archaeologist decipher some runes. He knows that this ancient society used a Base 10 system, and that they never start a number with a leading zero. He's figured out most of the digits as well as a few operators, but he needs your help to figure out the rest.

The professor will give you a simple math expression, of the form

```
[number][op][number]=[number]
```

He has converted all of the runes he knows into digits. The only operators he knows are addition (`+`),subtraction(`-`), and multiplication (`*`), so those are the only ones that will appear. Each number will be in the range from -1000000 to 1000000, and will consist of only the digits 0-9, possibly a leading -, and maybe a few ?s. If there are ?s in an expression, they represent a digit rune that the professor doesn't know (never an operator, and never a leading -). All of the ?s in an expression will represent the same digit (0-9), and it won't be one of the other given digits in the expression. No number will begin with a 0 unless the number itself is  0, therefore 00 would not be a valid number. 

Given an expression, figure out the value of the rune represented by the question mark. If more than one digit works, give the lowest one. If no digit works, well, that's bad news for the professor - it means that he's got some of his runes wrong. output -1 in that case.

Complete the method to solve the expression to find the value of the unknown rune. The method takes a string as a paramater repressenting the expression and will return an int value representing the unknown rune or -1 if no such rune exists.

~~~if:php
**Most of the time, the professor will be able to figure out most of the runes himself, but sometimes, there may be exactly 1 rune present in the expression that the professor cannot figure out (resulting in all question marks where the digits are in the expression) so be careful ;)**
~~~

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Genos needs your help. He was asked to solve the following programming problem by Saitama:

The length of some string s is denoted |s|. The Hamming distance between two strings s and t of equal length is defined as $\sum_{i = 1}^{|s|}|s_{i} - t_{i}|$, where s_{i} is the i-th character of s and t_{i} is the i-th character of t. For example, the Hamming distance between string "0011" and string "0110" is |0 - 0| + |0 - 1| + |1 - 1| + |1 - 0| = 0 + 1 + 0 + 1 = 2.

Given two binary strings a and b, find the sum of the Hamming distances between a and all contiguous substrings of b of length |a|.


-----Input-----

The first line of the input contains binary string a (1 ≤ |a| ≤ 200 000).

The second line of the input contains binary string b (|a| ≤ |b| ≤ 200 000).

Both strings are guaranteed to consist of characters '0' and '1' only.


-----Output-----

Print a single integer — the sum of Hamming distances between a and all contiguous substrings of b of length |a|.


-----Examples-----
Input
01
00111

Output
3

Input
0011
0110

Output
2



-----Note-----

For the first sample case, there are four contiguous substrings of b of length |a|: "00", "01", "11", and "11". The distance between "01" and "00" is |0 - 0| + |1 - 0| = 1. The distance between "01" and "01" is |0 - 0| + |1 - 1| = 0. The distance between "01" and "11" is |0 - 1| + |1 - 1| = 1. Last distance counts twice, as there are two occurrences of string "11". The sum of these edit distances is 1 + 0 + 1 + 1 = 3.

The second sample case is described in the statement.

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