vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Cubical Planet

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
You can find anything whatsoever in our Galaxy! A cubical planet goes round an icosahedral star. Let us introduce a system of axes so that the edges of the cubical planet are parallel to the coordinate axes and two opposite vertices lay in the points (0,<=0,<=0) and (1,<=1,<=1). Two flies live on the planet. At the moment they are sitting on two different vertices of the cubical planet. Your task is to determine whether they see each other or not. The flies see each other when the vertices they occupy lie on the same face of the cube.

Input Specification:
The first line contains three space-separated integers (0 or 1) — the coordinates of the first fly, the second line analogously contains the coordinates of the second fly.

Output Specification:
Output "YES" (without quotes) if the flies see each other. Otherwise, output "NO".

Demo Input:
['0 0 0\n0 1 0\n', '1 1 0\n0 1 0\n', '0 0 0\n1 1 1\n']

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

Note:
none

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

Define a function $ f $ that starts with $ 1 $ and takes a sequence of finite lengths as an argument as follows.

$ \ displaystyle f (\\ {a_1, a_2, \ ldots, a_n \\}) = \ sum_ {i = 1} ^ n {a_i} ^ i $

Given a sequence of length $ N $, $ X = \\ {x_1, x_2, \ ldots, x_N \\} $, $ f (X) for all subsequences $ X'$ except empty columns. ') Find $ and output the sum of them divided by $ 998244353 $. However, the subsequence subsequences shall be renumbered starting from $ 1 $ while maintaining the relative order in the original sequence. Also, even if two subsequences are the same as columns, if they are taken out at different positions, they shall be counted separately.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq N \ leq 10 ^ 6 $
* $ 1 \ leq x_i \ leq 10 ^ 6 $
* All inputs are integers

Input

The input is given in the following format.


$ N $
$ x_1 $ $ \ ldots $ $ x_N $


The first line is given the length $ N $. In the second row, the elements of the sequence $ X $ are given, separated by blanks.

Output

Find $ f (X') $ for all subsequences $ X'$ except empty columns, and divide the sum by $ 998244353 $ to output the remainder.

Examples

Input

3
1 2 3


Output

64


Input

5
100 200 300 400 500


Output

935740429

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a tree with N vertices numbered 1 to N.
The i-th edge in this tree connects Vertex a_i and Vertex b_i.

Consider painting each of these edges white or black. There are 2^{N-1} such ways to paint the edges. Among them, how many satisfy all of the following M restrictions?  
 - The i-th (1 \leq i \leq M) restriction is represented by two integers u_i and v_i, which mean that the path connecting Vertex u_i and Vertex v_i must contain at least one edge painted black.

-----Constraints-----
 - 2 \leq N \leq 50
 - 1 \leq a_i,b_i \leq N
 - The graph given in input is a tree.
 - 1 \leq M \leq \min(20,\frac{N(N-1)}{2})
 - 1 \leq u_i < v_i \leq N
 - If i \not= j, either u_i \not=u_j or v_i\not=v_j
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 b_1
:
a_{N-1} b_{N-1}
M
u_1 v_1
:
u_M v_M

-----Output-----
Print the number of ways to paint the edges that satisfy all of the M conditions.

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

-----Sample Output-----
3

The tree in this input is shown below:





All of the M restrictions will be satisfied if Edge 1 and 2 are respectively painted (white, black), (black, white), or (black, black), so the answer is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n incoming messages for Vasya. The i-th message is going to be received after t_{i} minutes. Each message has a cost, which equals to A initially. After being received, the cost of a message decreases by B each minute (it can become negative). Vasya can read any message after receiving it at any moment of time. After reading the message, Vasya's bank account receives the current cost of this message. Initially, Vasya's bank account is at 0.

Also, each minute Vasya's bank account receives C·k, where k is the amount of received but unread messages.

Vasya's messages are very important to him, and because of that he wants to have all messages read after T minutes.

Determine the maximum amount of money Vasya's bank account can hold after T minutes.


-----Input-----

The first line contains five integers n, A, B, C and T (1 ≤ n, A, B, C, T ≤ 1000).

The second string contains n integers t_{i} (1 ≤ t_{i} ≤ T).


-----Output-----

Output one integer  — the answer to the problem.


-----Examples-----
Input
4 5 5 3 5
1 5 5 4

Output
20

Input
5 3 1 1 3
2 2 2 1 1

Output
15

Input
5 5 3 4 5
1 2 3 4 5

Output
35



-----Note-----

In the first sample the messages must be read immediately after receiving, Vasya receives A points for each message, n·A = 20 in total.

In the second sample the messages can be read at any integer moment.

In the third sample messages must be read at the moment T. This way Vasya has 1, 2, 3, 4 and 0 unread messages at the corresponding minutes, he gets 40 points for them. When reading messages, he receives (5 - 4·3) + (5 - 3·3) + (5 - 2·3) + (5 - 1·3) + 5 =  - 5 points. This is 35 in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Fourier transformations are hard. Fouriest transformations are harder.

This Kata is based on the SMBC Comic on fourier transformations.

A fourier transformation on a number is one that converts the number to a base in which it has more `4`s ( `10` in base `6` is `14`, which has `1` four as opposed to none, hence, fourier in base `6` ).

A number's fouriest transformation converts it to the base in which it has the most `4`s.  
For example: `35353` is the fouriest in base `6`: `431401`.

This kata requires you to create a method `fouriest` that takes a number and makes it the fouriest, telling us in which base this happened, as follows:

```python
fouriest(number) -> "{number} is the fouriest ({fouriest_representation}) in base {base}"
```

## Important notes

* For this kata we don't care about digits greater than `9` ( only `0` to `9` ), so we will represent all digits greater than `9` as `'x'`: `10` in base `11` is `'x'`, `119` in base `20` is `'5x'`, `118` in base `20` is also `'5x'`

* When a number has several fouriest representations, we want the one with the LOWEST base

```if:haskell,javascript
* Numbers below `9` will not be tested
```

```if:javascript
* A `BigNumber` library has been provided; documentation is [here](https://mikemcl.github.io/bignumber.js/)
```

## Examples

```python
"30 is the fouriest (42) in base 7"
"15 is the fouriest (14) in base 11"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected graph with n vertices and m edges. Also, you are given an integer k.

Find either a clique of size k or a non-empty subset of vertices such that each vertex of this subset has at least k neighbors in the subset. If there are no such cliques and subsets report about it.

A subset of vertices is called a clique of size k if its size is k and there exists an edge between every two vertices from the subset. A vertex is called a neighbor of the other vertex if there exists an edge between them.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^5) — the number of test cases. The next lines contain descriptions of test cases.

The first line of the description of each test case contains three integers n, m, k (1 ≤ n, m, k ≤ 10^5, k ≤ n).

Each of the next m lines contains two integers u, v (1 ≤ u, v ≤ n, u ≠ v), denoting an edge between vertices u and v.

It is guaranteed that there are no self-loops or multiple edges. It is guaranteed that the sum of n for all test cases and the sum of m for all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case: 

If you found a subset of vertices such that each vertex of this subset has at least k neighbors in the subset in the first line output 1 and the size of the subset. On the second line output the vertices of the subset in any order.

If you found a clique of size k then in the first line output 2 and in the second line output the vertices of the clique in any order.

If there are no required subsets and cliques print -1.

If there exists multiple possible answers you can print any of them.

Example

Input


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


Output


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

Note

In the first test case: the subset \{1, 2, 3, 4\} is a clique of size 4.

In the second test case: degree of each vertex in the original graph is at least 3. So the set of all vertices is a correct answer.

In the third test case: there are no cliques of size 4 or required subsets, so the answer is -1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You've got a list of program warning logs. Each record of a log stream is a string in this format:  "2012-MM-DD HH:MM:SS:MESSAGE" (without the quotes). 

String "MESSAGE" consists of spaces, uppercase and lowercase English letters and characters "!", ".", ",", "?". String "2012-MM-DD" determines a correct date in the year of 2012. String "HH:MM:SS" determines a correct time in the 24 hour format.

The described record of a log stream means that at a certain time the record has got some program warning (string "MESSAGE" contains the warning's description).

Your task is to print the first moment of time, when the number of warnings for the last n seconds was not less than m.


-----Input-----

The first line of the input contains two space-separated integers n and m (1 ≤ n, m ≤ 10000).

The second and the remaining lines of the input represent the log stream. The second line of the input contains the first record of the log stream, the third line contains the second record and so on. Each record of the log stream has the above described format. All records are given in the chronological order, that is, the warning records are given in the order, in which the warnings appeared in the program. 

It is guaranteed that the log has at least one record. It is guaranteed that the total length of all lines of the log stream doesn't exceed 5·10^6 (in particular, this means that the length of some line does not exceed 5·10^6 characters). It is guaranteed that all given dates and times are correct, and the string 'MESSAGE" in all records is non-empty.


-----Output-----

If there is no sought moment of time, print -1. Otherwise print a string in the format "2012-MM-DD HH:MM:SS" (without the quotes) — the first moment of time when the number of warnings for the last n seconds got no less than m.


-----Examples-----
Input
60 3
2012-03-16 16:15:25: Disk size is
2012-03-16 16:15:25: Network failute
2012-03-16 16:16:29: Cant write varlog
2012-03-16 16:16:42: Unable to start process
2012-03-16 16:16:43: Disk size is too small
2012-03-16 16:16:53: Timeout detected

Output
2012-03-16 16:16:43

Input
1 2
2012-03-16 23:59:59:Disk size
2012-03-17 00:00:00: Network
2012-03-17 00:00:01:Cant write varlog

Output
-1

Input
2 2
2012-03-16 23:59:59:Disk size is too sm
2012-03-17 00:00:00:Network failute dete
2012-03-17 00:00:01:Cant write varlogmysq

Output
2012-03-17 00:00:00

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We are given a certain number ```n``` and we do the product partitions of it.
```[59, 3, 2, 2, 2]``` is a product partition of ```1416``` because:
```
59 * 3 * 2 * 2 * 2 = 1416
```
We form a score, ```sc``` for each partition in the following way:
- if ```d1, d2, ...., dk``` are the prime factors of ```n```, and ```f1, f2, ...., fk```, the corresponding frequencies for each factor, we calculate:



Suposse that we have that ```n = 1416``` 
The product partitions of this number with a corresponding special score are as follows:
```
Product Partition           Score(sc)
[59, 3, 2, 2, 2]             350    # equals to: (59^1 + 3^1 + 2^3) * 5
[177, 2, 2, 2]               740    # equals to: (177^1 + 2^3) * 4
[118, 3, 2, 2]               500
[59, 6, 2, 2]                276
[354, 2, 2]                 1074
[59, 4, 3, 2]                272
[236, 3, 2]                  723
[177, 4, 2]                  549
[118, 6, 2]                  378
[59, 12, 2]                  219
[708, 2]                    1420  <---- maximum value
[118, 4, 3]                  375
[59, 8, 3]                   210
[472, 3]                     950
[59, 6, 4]                   207
[354, 4]                     716
[236, 6]                     484
[177, 8]                     370
[118, 12]                    260
[59, 24]                     166  <---- minimum value
```
So we need a function that may give us the product partition with maximum or minimum score.

The function ```find_spec_prod_part()``` will receive two arguments:

- an integer ```n, n > 0```
- a command as a string, one of the following ones: ```'max' or 'min'```

The function should output a list with two elements: the found product partition (as a list sorted in descendin order) with its corresponding score.
```
find_spec_prod_part(n, com) ---> [prod_partition, score]
```
Let'see some cases:
```python
find_spec_prod_part(1416, 'max') == [[708, 2], 1420]

find_spec_prod_part(1416, 'min') == [[59, 24], 166]
```

The function should reject prime numbers:
```python
find_spec_prod_part(10007 , 'max') == "It is a prime number"
```
Enjoy it!

Hint: In this kata, optimization is one of the purposes or tags. The algorithm to produce the product partition is a key factor in terms of speed. Your code will be tested for an ```n``` value up to ```500000```.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a rectangular cake, represented as an *r*<=×<=*c* grid. Each cell either has an evil strawberry, or is empty. For example, a 3<=×<=4 cake may look as follows:

The cakeminator is going to eat the cake! Each time he eats, he chooses a row or a column that does not contain any evil strawberries and contains at least one cake cell that has not been eaten before, and eats all the cake cells there. He may decide to eat any number of times.

Please output the maximum number of cake cells that the cakeminator can eat.

Input Specification:
The first line contains two integers *r* and *c* (2<=≤<=*r*,<=*c*<=≤<=10), denoting the number of rows and the number of columns of the cake. The next *r* lines each contains *c* characters — the *j*-th character of the *i*-th line denotes the content of the cell at row *i* and column *j*, and is either one of these: 
 -  '.' character denotes a cake cell with no evil strawberry; -  'S' character denotes a cake cell with an evil strawberry.

Output Specification:
Output the maximum number of cake cells that the cakeminator can eat.

Demo Input:
['3 4\nS...\n....\n..S.\n']

Demo Output:
['8\n']

Note:
For the first example, one possible way to eat the maximum number of cake cells is as follows (perform 3 eats).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On a broken calculator that has a number showing on its display, we can perform two operations:

Double: Multiply the number on the display by 2, or;
Decrement: Subtract 1 from the number on the display.

Initially, the calculator is displaying the number X.
Return the minimum number of operations needed to display the number Y.
 
Example 1:
Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:
Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:
Input: X = 3, Y = 10
Output: 3
Explanation:  Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:
Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

 
Note:

1 <= X <= 10^9
1 <= Y <= 10^9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Willem, Chtholly and Seniorious

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
— Willem...

— What's the matter?

— It seems that there's something wrong with Seniorious...

— I'll have a look...



Seniorious is made by linking special talismans in particular order.

After over 500 years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.

Seniorious has *n* pieces of talisman. Willem puts them in a line, the *i*-th of which is an integer *a**i*.

In order to maintain it, Willem needs to perform *m* operations.

There are four types of operations:
-  1 *l* *r* *x*: For each *i* such that *l*<=≤<=*i*<=≤<=*r*, assign *a**i*<=+<=*x* to *a**i*.-  2 *l* *r* *x*: For each *i* such that *l*<=≤<=*i*<=≤<=*r*, assign *x* to *a**i*.-  3 *l* *r* *x*: Print the *x*-th smallest number in the index range [*l*,<=*r*], i.e. the element at the *x*-th position if all the elements *a**i* such that *l*<=≤<=*i*<=≤<=*r* are taken and sorted into an array of non-decreasing integers. It's guaranteed that 1<=≤<=*x*<=≤<=*r*<=-<=*l*<=+<=1.-  4 *l* *r* *x* *y*: Print the sum of the *x*-th power of *a**i* such that *l*<=≤<=*i*<=≤<=*r*, modulo *y*, i.e. .

Input Specification:
The only line contains four integers *n*,<=*m*,<=*seed*,<=*v**max* (1<=≤<=*n*,<=*m*<=≤<=105,<=0<=≤<=*seed*<=&lt;<=109<=+<=7,<=1<=≤<=*vmax*<=≤<=109).

The initial values and operations are generated using following pseudo code:

Here *op* is the type of the operation mentioned in the legend.

Output Specification:
For each operation of types 3 or 4, output a line containing the answer.

Demo Input:
['10 10 7 9\n', '10 10 9 9\n']

Demo Output:
['2\n1\n0\n3\n', '1\n1\n3\n3\n']

Note:
In the first example, the initial array is {8, 9, 7, 2, 3, 1, 5, 6, 4, 8}.

The operations are:
 -  2 6 7 9 -  1 3 10 8 -  4 4 6 2 4 -  1 4 5 8 -  2 1 7 1 -  4 7 9 4 4 -  1 2 7 9 -  4 5 8 1 1 -  2 5 7 5 -  4 3 10 8 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given strings A, B, and C, find whether C is formed by an interleaving of A and B.
An interleaving of two strings S and T is a configuration such that it creates a new string Y from the concatenation substrings of A and B and |Y| = |A + B| = |C|
For example:
A = "XYZ"
B = "ABC"
so we can make multiple interleaving string Y like, XYZABC, XAYBCZ, AXBYZC, XYAZBC and many more so here your task is to check whether you can create a string Y which can be equal to C.
Specifically, you just need to create substrings of string A and create substrings B and concatenate them and check whether it is equal to C or not.
Note: a + b is the concatenation of strings a and b.
Return true if C is formed by an interleaving of A and B, else return false.
Example 1:
Input:
A = YX, B = X, C = XXY
Output: 0
Explanation: XXY is not interleaving
of YX and X
Example 2:
Input:
A = XY, B = X, C = XXY
Output: 1
Explanation: XXY is interleaving of
XY and X.
Your Task:
Complete the function isInterleave() which takes three strings A, B and C as input and returns true if C is an interleaving of A and B else returns false. (1 is printed by the driver code if the returned value is true, otherwise 0.)
Expected Time Complexity: O(N * M)
Expected Auxiliary Space: O(N * M)
here, N = length of A, and M = length of B
Constraints:
1 ≤ length of A, B ≤ 100
1 ≤ length of C ≤ 200

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja has an n × m rectangular table a, each cell of the table contains a zero or a number one. Sereja wants his table to meet the following requirement: each connected component of the same values forms a rectangle with sides parallel to the sides of the table. Rectangles should be filled with cells, that is, if a component form a rectangle of size h × w, then the component must contain exactly hw cells.

A connected component of the same values is a set of cells of the table that meet the following conditions:  every two cells of the set have the same value;  the cells of the set form a connected region on the table (two cells are connected if they are adjacent in some row or some column of the table);  it is impossible to add any cell to the set unless we violate the two previous conditions. 

Can Sereja change the values of at most k cells of the table so that the table met the described requirement? What minimum number of table cells should he change in this case?


-----Input-----

The first line contains integers n, m and k (1 ≤ n, m ≤ 100; 1 ≤ k ≤ 10). Next n lines describe the table a: the i-th of them contains m integers a_{i}1, a_{i}2, ..., a_{im} (0 ≤ a_{i}, j ≤ 1) — the values in the cells of the i-th row.


-----Output-----

Print -1, if it is impossible to meet the requirement. Otherwise, print the minimum number of cells which should be changed.


-----Examples-----
Input
5 5 2
1 1 1 1 1
1 1 1 1 1
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1

Output
1

Input
3 4 1
1 0 0 0
0 1 1 1
1 1 1 0

Output
-1

Input
3 4 1
1 0 0 1
0 1 1 0
1 0 0 1

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given an array $a$ of length $2n$. Is it possible to reorder it in such way so that the sum of the first $n$ elements isn't equal to the sum of the last $n$ elements?


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 1000$), where $2n$ is the number of elements in the array $a$.

The second line contains $2n$ space-separated integers $a_1$, $a_2$, $\ldots$, $a_{2n}$ ($1 \le a_i \le 10^6$) — the elements of the array $a$.


-----Output-----

If there's no solution, print "-1" (without quotes). Otherwise, print a single line containing $2n$ space-separated integers. They must form a reordering of $a$. You are allowed to not change the order.


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

Output
2 1 3 1 1 2
Input
1
1 1

Output
-1


-----Note-----

In the first example, the first $n$ elements have sum $2+1+3=6$ while the last $n$ elements have sum $1+1+2=4$. The sums aren't equal.

In the second example, there's no solution.

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