vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Masha has n types of tiles of size 2 × 2. Each cell of the tile contains one integer. Masha has an infinite number of tiles of each type.

Masha decides to construct the square of size m × m consisting of the given tiles. This square also has to be a symmetric with respect to the main diagonal matrix, and each cell of this square has to be covered with exactly one tile cell, and also sides of tiles should be parallel to the sides of the square. All placed tiles cannot intersect with each other. Also, each tile should lie inside the square. See the picture in Notes section for better understanding.

Symmetric with respect to the main diagonal matrix is such a square s that for each pair (i, j) the condition s[i][j] = s[j][i] holds. I.e. it is true that the element written in the i-row and j-th column equals to the element written in the j-th row and i-th column.

Your task is to determine if Masha can construct a square of size m × m which is a symmetric matrix and consists of tiles she has. Masha can use any number of tiles of each type she has to construct the square. Note that she can not rotate tiles, she can only place them in the orientation they have in the input.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 100) — the number of test cases. Then t test cases follow.

The first line of the test case contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of types of tiles and the size of the square Masha wants to construct.

The next 2n lines of the test case contain descriptions of tiles types. Types of tiles are written one after another, each type is written on two lines. 

The first line of the description contains two positive (greater than zero) integers not exceeding 100 — the number written in the top left corner of the tile and the number written in the top right corner of the tile of the current type. The second line of the description contains two positive (greater than zero) integers not exceeding 100 — the number written in the bottom left corner of the tile and the number written in the bottom right corner of the tile of the current type.

It is forbidden to rotate tiles, it is only allowed to place them in the orientation they have in the input.

Output

For each test case print the answer: "YES" (without quotes) if Masha can construct the square of size m × m which is a symmetric matrix. Otherwise, print "NO" (withtout quotes).

Example

Input


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


Output


YES
NO
YES
NO
YES
YES

Note

The first test case of the input has three types of tiles, they are shown on the picture below.

<image>

Masha can construct, for example, the following square of size 4 × 4 which is a symmetric matrix:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pavel cooks barbecue. There are n skewers, they lay on a brazier in a row, each on one of n positions. Pavel wants each skewer to be cooked some time in every of n positions in two directions: in the one it was directed originally and in the reversed direction.

Pavel has a plan: a permutation p and a sequence b_1, b_2, ..., b_{n}, consisting of zeros and ones. Each second Pavel move skewer on position i to position p_{i}, and if b_{i} equals 1 then he reverses it. So he hope that every skewer will visit every position in both directions.

Unfortunately, not every pair of permutation p and sequence b suits Pavel. What is the minimum total number of elements in the given permutation p and the given sequence b he needs to change so that every skewer will visit each of 2n placements? Note that after changing the permutation should remain a permutation as well.

There is no problem for Pavel, if some skewer visits some of the placements several times before he ends to cook. In other words, a permutation p and a sequence b suit him if there is an integer k (k ≥ 2n), so that after k seconds each skewer visits each of the 2n placements.

It can be shown that some suitable pair of permutation p and sequence b exists for any n.


-----Input-----

The first line contain the integer n (1 ≤ n ≤ 2·10^5) — the number of skewers.

The second line contains a sequence of integers p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ n) — the permutation, according to which Pavel wants to move the skewers.

The third line contains a sequence b_1, b_2, ..., b_{n} consisting of zeros and ones, according to which Pavel wants to reverse the skewers.


-----Output-----

Print single integer — the minimum total number of elements in the given permutation p and the given sequence b he needs to change so that every skewer will visit each of 2n placements.


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

Output
2

Input
3
2 3 1
0 0 0

Output
1



-----Note-----

In the first example Pavel can change the permutation to 4, 3, 1, 2.

In the second example Pavel can change any element of b to 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rachel works at a big Raf Laurens. There is a big event coming up and she has to select dresses for an exhibition.
She has N dresses numbered 1 to N. There are total 62 types of dresses, each represented by a different alphanumeric character (a-z, A-Z, 0-9). The N dresses are represented by a string S of length N of alphanumeric characters. The ith character of S denotes the type of the ith dress. Rachel will select two integers, A and B such that 1 ≤ A ≤ B ≤ N and take the dresses numbered from A to B to the exhibition.

Out of the 62 dress types, K dress types are special. Find the number of values of A and B possible such that the total number of special dresses of any type selected are atleast L and atmost R.

Input:

The first line of the input contains T, the number of test cases. The first line of each test case contains N, K, L and R. The second line of each test case contains the string of length N that denotes the type of the N dresses. The third line contains another string of length K, denoting the types of the special dresses

Output:

For each test case, output the number of ways to select A and B.

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 104
1 ≤ K ≤ 62
0 ≤ L ≤ R ≤ N
S contains alphanumeric characters: (a-z, A-Z and 0-9)

SAMPLE INPUT
2
5 3 3 4
AbcAb
AbZ
9 2 1 2
adebfgbhd
ab

SAMPLE OUTPUT
3
33

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.
 
Example 1:
Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].
Example 2:
Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.

Example 3:
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

 
Constraints:

1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the given LFUCache Class with the following description.
LFUCache(int capacity): This Initializes the object with the capacity of the data structure.
int get(int key): Returns the value of the given key if it exists or else returns -1.
void put(int key, int value): If the key is already present, then update its value and if the key is not present, then it should be inserted. If the data  structure has reached its maximum capacity, then the least frequently used (LFU) key should be invalidated and removed. If during removal, more than one key has same frequency, then the Least Recently Used (LRU) key amongst them should be removed.
Example:
Input: 
Capacity: 3
put(5,7)put(4,6)put(3,5)put(2,4)put(1,3)
get(1)get(2)get(3)get(4)get(5)
Output: 
3
4
5
-1
-1
Explanation: 
When put(2,4) is executed, (5,7) gets invalidated. Similarly when put(1,3) is executed, (4,6) gets invalidated. Therefore only the values for key 1,2,3 are present in the cache after all the put operations.
Your Task:
Implement the given functions, void put(int key, int value) and int get(int key). 
The functions get and put must each run in O(1) average time complexity.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
0 <= capacity <= 10^{4}
0 <= key <= 10^{5}
0 <= value <= 10^{6}
At most 2 *10^{5} calls will be made to get and put.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three strings $a$, $b$ and $c$ of the same length $n$. The strings consist of lowercase English letters only. The $i$-th letter of $a$ is $a_i$, the $i$-th letter of $b$ is $b_i$, the $i$-th letter of $c$ is $c_i$.

For every $i$ ($1 \leq i \leq n$) you must swap (i.e. exchange) $c_i$ with either $a_i$ or $b_i$. So in total you'll perform exactly $n$ swap operations, each of them either $c_i \leftrightarrow a_i$ or $c_i \leftrightarrow b_i$ ($i$ iterates over all integers between $1$ and $n$, inclusive).

For example, if $a$ is "code", $b$ is "true", and $c$ is "help", you can make $c$ equal to "crue" taking the $1$-st and the $4$-th letters from $a$ and the others from $b$. In this way $a$ becomes "hodp" and $b$ becomes "tele".

Is it possible that after these swaps the string $a$ becomes exactly the same as the string $b$?


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 100$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a string of lowercase English letters $a$.

The second line of each test case contains a string of lowercase English letters $b$.

The third line of each test case contains a string of lowercase English letters $c$.

It is guaranteed that in each test case these three strings are non-empty and have the same length, which is not exceeding $100$.


-----Output-----

Print $t$ lines with answers for all test cases. For each test case:

If it is possible to make string $a$ equal to string $b$ print "YES" (without quotes), otherwise print "NO" (without quotes).

You can print either lowercase or uppercase letters in the answers.


-----Example-----
Input
4
aaa
bbb
ccc
abc
bca
bca
aabb
bbaa
baba
imi
mii
iim

Output
NO
YES
YES
NO



-----Note-----

In the first test case, it is impossible to do the swaps so that string $a$ becomes exactly the same as string $b$.

In the second test case, you should swap $c_i$ with $a_i$ for all possible $i$. After the swaps $a$ becomes "bca", $b$ becomes "bca" and $c$ becomes "abc". Here the strings $a$ and $b$ are equal.

In the third test case, you should swap $c_1$ with $a_1$, $c_2$ with $b_2$, $c_3$ with $b_3$ and $c_4$ with $a_4$. Then string $a$ becomes "baba", string $b$ becomes "baba" and string $c$ becomes "abab". Here the strings $a$ and $b$ are equal.

In the fourth test case, it is impossible to do the swaps so that string $a$ becomes exactly the same as string $b$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is throwing a party for his N friends. There is a pizza store nearby and he wants to buy pizza for his friends. Each pizza has exactly K slices. Chef's friends get sad if one gets more slices than the other. Also, Chef gets sad if there are some pizza slices left. More formally, suppose Chef buys P pizzas, then everyone is happy if and only if there is a way to distribute K \cdot P slices between N friends.

You need to find the minimum number of pizzas Chef has to buy to share all the slices among his friends so that none of his friends gets sad. Note that Chef hates pizza and doesn't take any slices.

------ Input Format ------ 

- First line of input contains T, the number of test cases. Then the test cases follow.
- Each test case contains two space-separated integers N and K, where N is the number of friends of chef and K is the number of slices in a pizza.

------ Output Format ------ 

For each test case, print the minimum number of pizzas chef has to buy to share among his friends so that none of his friends gets sad.

------ Constraints ------ 

$1 ≤ T ≤ 2 \cdot 10^{5}$
$1 ≤ N, K ≤ 10^{9}$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

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

----- Sample Output 1 ------ 
1
2
2

----- explanation 1 ------ 
- Test case $1$: One pizza has $2$ slices. And there are $2$ friends. So chef can just buy one pizza and give one slice to one friend and another slice to another friend.
- Test case $2$: One pizza has $3$ slices. And there are $2$ friends. So chef can't share one pizza without being left out with a slice. So he needs to buy at least $2$ pizzas. And if he buys $2$ pizzas, he can give $3$ slices to one friend and $3$ to another. So the minimum number of pizzas chef needs to buy is equal to $2$.
- Test case $3$: One pizza has $2$ slices. And there are $4$ friends. So chef can't share one pizza among the $4$ friends. So he needs to buy at least $2$ pizzas. And if he buys $2$ pizzas, he can give $1$ slice to each of his friends. So the minimum number of pizzas chef needs to buy is equal to $2$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vova promised himself that he would never play computer games... But recently Firestorm — a well-known game developing company — published their newest game, World of Farcraft, and it became really popular. Of course, Vova started playing it.

Now he tries to solve a quest. The task is to come to a settlement named Overcity and spread a rumor in it.

Vova knows that there are *n* characters in Overcity. Some characters are friends to each other, and they share information they got. Also Vova knows that he can bribe each character so he or she starts spreading the rumor; *i*-th character wants *c**i* gold in exchange for spreading the rumor. When a character hears the rumor, he tells it to all his friends, and they start spreading the rumor to their friends (for free), and so on.

The quest is finished when all *n* characters know the rumor. What is the minimum amount of gold Vova needs to spend in order to finish the quest?

Take a look at the notes if you think you haven't understood the problem completely.

Input Specification:
The first line contains two integer numbers *n* and *m* (1<=≤<=*n*<=≤<=105,<=0<=≤<=*m*<=≤<=105) — the number of characters in Overcity and the number of pairs of friends.

The second line contains *n* integer numbers *c**i* (0<=≤<=*c**i*<=≤<=109) — the amount of gold *i*-th character asks to start spreading the rumor.

Then *m* lines follow, each containing a pair of numbers (*x**i*,<=*y**i*) which represent that characters *x**i* and *y**i* are friends (1<=≤<=*x**i*,<=*y**i*<=≤<=*n*, *x**i*<=≠<=*y**i*). It is guaranteed that each pair is listed at most once.

Output Specification:
Print one number — the minimum amount of gold Vova has to spend in order to finish the quest.

Demo Input:
['5 2\n2 5 3 4 8\n1 4\n4 5\n', '10 0\n1 2 3 4 5 6 7 8 9 10\n', '10 5\n1 6 2 7 3 8 4 9 5 10\n1 2\n3 4\n5 6\n7 8\n9 10\n']

Demo Output:
['10\n', '55\n', '15\n']

Note:
In the first example the best decision is to bribe the first character (he will spread the rumor to fourth character, and the fourth one will spread it to fifth). Also Vova has to bribe the second and the third characters, so they know the rumor.

In the second example Vova has to bribe everyone.

In the third example the optimal decision is to bribe the first, the third, the fifth, the seventh and the ninth characters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Python, a string of text can be aligned left, right and center.

.ljust(width)

This method returns a left aligned string of length width.

>>> width = 20
>>> print 'HackerRank'.ljust(width,'-')
HackerRank----------  

.center(width)

This method returns a centered string of length width.

>>> width = 20
>>> print 'HackerRank'.center(width,'-')
-----HackerRank-----

.rjust(width)

This method returns a right aligned string of length width.

>>> width = 20
>>> print 'HackerRank'.rjust(width,'-')
----------HackerRank

Task

You are given a partial code that is used for generating the HackerRank Logo of variable thickness. 

Your task is to replace the blank (______) with rjust, ljust or center.

Input Format

A single line containing the thickness value for the logo.

Constraints  

The thickness must be an odd number. 

$0<thickness<50$

Output Format

Output the desired logo.

Sample Input
5

Sample Output
    H    
   HHH   
  HHHHH  
 HHHHHHH 
HHHHHHHHH
  HHHHH               HHHHH             
  HHHHH               HHHHH             
  HHHHH               HHHHH             
  HHHHH               HHHHH             
  HHHHH               HHHHH             
  HHHHH               HHHHH             
  HHHHHHHHHHHHHHHHHHHHHHHHH   
  HHHHHHHHHHHHHHHHHHHHHHHHH   
  HHHHHHHHHHHHHHHHHHHHHHHHH   
  HHHHH               HHHHH             
  HHHHH               HHHHH             
  HHHHH               HHHHH             
  HHHHH               HHHHH             
  HHHHH               HHHHH             
  HHHHH               HHHHH             
                    HHHHHHHHH 
                     HHHHHHH  
                      HHHHH   
                       HHH    
                        H

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Gerald has *n* younger brothers and their number happens to be even. One day he bought *n*2 candy bags. One bag has one candy, one bag has two candies, one bag has three candies and so on. In fact, for each integer *k* from 1 to *n*2 he has exactly one bag with *k* candies. 

Help him give *n* bags of candies to each brother so that all brothers got the same number of candies.

Input Specification:
The single line contains a single integer *n* (*n* is even, 2<=≤<=*n*<=≤<=100) — the number of Gerald's brothers.

Output Specification:
Let's assume that Gerald indexes his brothers with numbers from 1 to *n*. You need to print *n* lines, on the *i*-th line print *n* integers — the numbers of candies in the bags for the *i*-th brother. Naturally, all these numbers should be distinct and be within limits from 1 to *n*2. You can print the numbers in the lines in any order. 

It is guaranteed that the solution exists at the given limits.

Demo Input:
['2\n']

Demo Output:
['1 4\n2 3\n']

Note:
The sample shows Gerald's actions if he has two brothers. In this case, his bags contain 1, 2, 3 and 4 candies. He can give the bags with 1 and 4 candies to one brother and the bags with 2 and 3 to the other brother.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a$ consisting of $n$ positive integers. Find a non-empty subset of its elements such that their sum is even (i.e. divisible by $2$) or determine that there is no such subset.

Both the given array and required subset may contain equal values.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 100$), number of test cases to solve. Descriptions of $t$ test cases follow.

A description of each test case consists of two lines. The first line contains a single integer $n$ ($1 \leq n \leq 100$), length of array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 100$), elements of $a$. The given array $a$ can contain equal values (duplicates).


-----Output-----

For each test case output $-1$ if there is no such subset of elements. Otherwise output positive integer $k$, number of elements in the required subset. Then output $k$ distinct integers ($1 \leq p_i \leq n$), indexes of the chosen elements. If there are multiple solutions output any of them.


-----Example-----
Input
3
3
1 4 3
1
15
2
3 5

Output
1
2
-1
2
1 2



-----Note-----

There are three test cases in the example.

In the first test case, you can choose the subset consisting of only the second element. Its sum is $4$ and it is even.

In the second test case, there is only one non-empty subset of elements consisting of the first element, however sum in it is odd, so there is no solution.

In the third test case, the subset consisting of all array's elements has even sum.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let $\mathsf{AND}$ denote the bitwise AND operation , and $\mathsf{OR}$ denote the bitwise OR operation .

You are given an array $a$ of length $n$ and a non-negative integer $k$. You can perform at most $k$ operations on the array of the following type:

Select an index $i$ ($1 \leq i \leq n$) and replace $a_i$ with $a_i$ $\mathsf{OR}$ $2^j$ where $j$ is any integer between $0$ and $30$ inclusive. In other words, in an operation you can choose an index $i$ ($1 \leq i \leq n$) and set the $j$-th bit of $a_i$ to $1$ ($0 \leq j \leq 30$).

Output the maximum possible value of $a_1$ $\mathsf{AND}$ $a_2$ $\mathsf{AND}$ $\dots$ $\mathsf{AND}$ $a_n$ after performing at most $k$ operations.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains the integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le 10^9$).

Then a single line follows, containing $n$ integers describing the arrays $a$ ($0 \leq a_i < 2^{31}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output a single line containing the maximum possible $\mathsf{AND}$ value of $a_1$ $\mathsf{AND}$ $a_2$ $\mathsf{AND}$ $\dots$ $\mathsf{AND}$ $a_n$ after performing at most $k$ operations.


-----Examples-----

Input
4
3 2
2 1 1
7 0
4 6 6 28 6 6 12
1 30
0
4 4
3 1 3 1
Output
2
4
2147483646
1073741825


-----Note-----

For the first test case, we can set the bit $1$ ($2^1$) of the last $2$ elements using the $2$ operations, thus obtaining the array [$2$, $3$, $3$], which has $\mathsf{AND}$ value equal to $2$.

For the second test case, we can't perform any operations so the answer is just the $\mathsf{AND}$ of the whole array which is $4$.

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