meetforever/GRPO_CL huggingface dataset:
user: Lindsey Buckingham told Stevie Nicks "Go your own way". Nicks is now sad and wants to go away as quickly as possible, but she lives in a 2D hexagonal world.

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

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

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


-----Input-----

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

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

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


-----Output-----

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


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

Output
18
1000000000000000000



-----Note-----

The picture below shows the solution for the first sample. The cost $18$ is reached by taking $c_3$ 3 times and $c_2$ once, amounting to $5+5+5+3=18$. [Image]
user: Recently a new building with a new layout was constructed in Monocarp's hometown. According to this new layout, the building consists of three types of apartments: three-room, five-room, and seven-room apartments. It's also known that each room of each apartment has exactly one window. In other words, a three-room apartment has three windows, a five-room — five windows, and a seven-room — seven windows.

Monocarp went around the building and counted $n$ windows. Now he is wondering, how many apartments of each type the building may have.

Unfortunately, Monocarp only recently has learned to count, so he is asking you to help him to calculate the possible quantities of three-room, five-room, and seven-room apartments in the building that has $n$ windows. If there are multiple answers, you can print any of them.

Here are some examples:

  if Monocarp has counted $30$ windows, there could have been $2$ three-room apartments, $2$ five-room apartments and $2$ seven-room apartments, since $2 \cdot 3 + 2 \cdot 5 + 2 \cdot 7 = 30$;  if Monocarp has counted $67$ windows, there could have been $7$ three-room apartments, $5$ five-room apartments and $3$ seven-room apartments, since $7 \cdot 3 + 5 \cdot 5 + 3 \cdot 7 = 67$;  if Monocarp has counted $4$ windows, he should have mistaken since no building with the aforementioned layout can have $4$ windows. 


-----Input-----

Th first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The only line of each test case contains one integer $n$ ($1 \le n \le 1000$) — the number of windows in the building.


-----Output-----

For each test case, if a building with the new layout and the given number of windows just can't exist, print $-1$.

Otherwise, print three non-negative integers — the possible number of three-room, five-room, and seven-room apartments. If there are multiple answers, print any of them.


-----Example-----
Input
4
30
67
4
14

Output
2 2 2
7 5 3
-1
0 0 2
user: The Resistance is trying to take control over all planets in a particular solar system. This solar system is shaped like a tree. More precisely, some planets are connected by bidirectional hyperspace tunnels in such a way that there is a path between every pair of the planets, but removing any tunnel would disconnect some of them.

The Resistance already has measures in place that will, when the time is right, enable them to control every planet that is not remote. A planet is considered to be remote if it is connected to the rest of the planets only via a single hyperspace tunnel.

How much work is there left to be done: that is, how many remote planets are there?


-----Input-----

The first line of the input contains an integer N (2 ≤ N ≤ 1000) – the number of planets in the galaxy.

The next N - 1 lines describe the hyperspace tunnels between the planets. Each of the N - 1 lines contains two space-separated integers u and v (1 ≤ u, v ≤ N) indicating that there is a bidirectional hyperspace tunnel between the planets u and v. It is guaranteed that every two planets are connected by a path of tunnels, and that each tunnel connects a different pair of planets.


-----Output-----

A single integer denoting the number of remote planets.


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

Output
3

Input
4
1 2
4 3
1 4

Output
2



-----Note-----

In the first example, only planets 2, 3 and 5 are connected by a single tunnel.

In the second example, the remote planets are 2 and 3.

Note that this problem has only two versions – easy and medium.
user: Santa Claus has received letters from $n$ different kids throughout this year. Of course, each kid wants to get some presents from Santa: in particular, the $i$-th kid asked Santa to give them one of $k_i$ different items as a present. Some items could have been asked by multiple kids.

Santa is really busy, so he wants the New Year Bot to choose the presents for all children. Unfortunately, the Bot's algorithm of choosing presents is bugged. To choose a present for some kid, the Bot does the following:

  choose one kid $x$ equiprobably among all $n$ kids;  choose some item $y$ equiprobably among all $k_x$ items kid $x$ wants;  choose a kid $z$ who will receive the present equipropably among all $n$ kids (this choice is independent of choosing $x$ and $y$); the resulting triple $(x, y, z)$ is called the decision of the Bot. 

If kid $z$ listed item $y$ as an item they want to receive, then the decision valid. Otherwise, the Bot's choice is invalid.

Santa is aware of the bug, but he can't estimate if this bug is really severe. To do so, he wants to know the probability that one decision generated according to the aforementioned algorithm is valid. Can you help him?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 10^6$) — the number of kids who wrote their letters to Santa.

Then $n$ lines follow, the $i$-th of them contains a list of items wanted by the $i$-th kid in the following format: $k_i$ $a_{i, 1}$ $a_{i, 2}$ ... $a_{i, k_i}$ ($1 \le k_i, a_{i, j} \le 10^6$), where $k_i$ is the number of items wanted by the $i$-th kid, and $a_{i, j}$ are the items themselves. No item is contained in the same list more than once.

It is guaranteed that $\sum \limits_{i = 1}^{n} k_i \le 10^6$.


-----Output-----

Print the probatility that the Bot produces a valid decision as follows:

Let this probability be represented as an irreducible fraction $\frac{x}{y}$. You have to print $x \cdot y^{-1} \mod 998244353$, where $y^{-1}$ is the inverse element of $y$ modulo $998244353$ (such integer that $y \cdot y^{-1}$ has remainder $1$ modulo $998244353$). 


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

Output
124780545

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

Output
798595483
user: Can the greatest common divisor and bitwise operations have anything in common? It is time to answer this question.

Suppose you are given a positive integer $a$. You want to choose some integer $b$ from $1$ to $a - 1$ inclusive in such a way that the greatest common divisor (GCD) of integers $a \oplus b$ and $a \> \& \> b$ is as large as possible. In other words, you'd like to compute the following function:

$$f(a) = \max_{0 < b < a}{gcd(a \oplus b, a \> \& \> b)}.$$

Here $\oplus$ denotes the bitwise XOR operation, and $\&$ denotes the bitwise AND operation.

The greatest common divisor of two integers $x$ and $y$ is the largest integer $g$ such that both $x$ and $y$ are divided by $g$ without remainder.

You are given $q$ integers $a_1, a_2, \ldots, a_q$. For each of these integers compute the largest possible value of the greatest common divisor (when $b$ is chosen optimally). 


-----Input-----

The first line contains an integer $q$ ($1 \le q \le 10^3$) — the number of integers you need to compute the answer for.

After that $q$ integers are given, one per line: $a_1, a_2, \ldots, a_q$ ($2 \le a_i \le 2^{25} - 1$) — the integers you need to compute the answer for. 


-----Output-----

For each integer, print the answer in the same order as the integers are given in input.


-----Example-----
Input
3
2
3
5

Output
3
1
7



-----Note-----

For the first integer the optimal choice is $b = 1$, then $a \oplus b = 3$, $a \> \& \> b = 0$, and the greatest common divisor of $3$ and $0$ is $3$.

For the second integer one optimal choice is $b = 2$, then $a \oplus b = 1$, $a \> \& \> b = 2$, and the greatest common divisor of $1$ and $2$ is $1$.

For the third integer the optimal choice is $b = 2$, then $a \oplus b = 7$, $a \> \& \> b = 0$, and the greatest common divisor of $7$ and $0$ is $7$.
user: 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.
user: Yurii is sure he can do everything. Can he solve this task, though?

He has an array $a$ consisting of $n$ positive integers. Let's call a subarray $a[l...r]$ good if the following conditions are simultaneously satisfied:   $l+1 \leq r-1$, i. e. the subarray has length at least $3$;  $(a_l \oplus a_r) = (a_{l+1}+a_{l+2}+\ldots+a_{r-2}+a_{r-1})$, where $\oplus$ denotes the bitwise XOR operation. 

In other words, a subarray is good if the bitwise XOR of the two border elements is equal to the sum of the rest of the elements. 

Yurii wants to calculate the total number of good subarrays. What is it equal to?

An array $c$ is a subarray of an array $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.


-----Input-----

The first line contains a single integer $n$ ($3 \leq n \leq 2\cdot 10^5$) — the length of $a$. 

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \lt 2^{30}$) — elements of $a$. 


-----Output-----

Output a single integer — the number of good subarrays. 


-----Examples-----
Input
8
3 1 2 3 1 2 3 15

Output
6
Input
10
997230370 58052053 240970544 715275815 250707702 156801523 44100666 64791577 43523002 480196854

Output
2


-----Note-----

There are $6$ good subarrays in the example:   $[3,1,2]$ (twice) because $(3 \oplus 2) = 1$;  $[1,2,3]$ (twice) because $(1 \oplus 3) = 2$;  $[2,3,1]$ because $(2 \oplus 1) = 3$;  $[3,1,2,3,1,2,3,15]$ because $(3 \oplus 15) = (1+2+3+1+2+3)$.
user: You are given a string $s$. You can build new string $p$ from $s$ using the following operation no more than two times:   choose any subsequence $s_{i_1}, s_{i_2}, \dots, s_{i_k}$ where $1 \le i_1 < i_2 < \dots < i_k \le |s|$;  erase the chosen subsequence from $s$ ($s$ can become empty);  concatenate chosen subsequence to the right of the string $p$ (in other words, $p = p + s_{i_1}s_{i_2}\dots s_{i_k}$). 

Of course, initially the string $p$ is empty. 

For example, let $s = \text{ababcd}$. At first, let's choose subsequence $s_1 s_4 s_5 = \text{abc}$ — we will get $s = \text{bad}$ and $p = \text{abc}$. At second, let's choose $s_1 s_2 = \text{ba}$ — we will get $s = \text{d}$ and $p = \text{abcba}$. So we can build $\text{abcba}$ from $\text{ababcd}$.

Can you build a given string $t$ using the algorithm above?


-----Input-----

The first line contains the single integer $T$ ($1 \le T \le 100$) — the number of test cases.

Next $2T$ lines contain test cases — two per test case. The first line contains string $s$ consisting of lowercase Latin letters ($1 \le |s| \le 400$) — the initial string.

The second line contains string $t$ consisting of lowercase Latin letters ($1 \le |t| \le |s|$) — the string you'd like to build.

It's guaranteed that the total length of strings $s$ doesn't exceed $400$.


-----Output-----

Print $T$ answers — one per test case. Print YES (case insensitive) if it's possible to build $t$ and NO (case insensitive) otherwise.


-----Example-----
Input
4
ababcd
abcba
a
b
defi
fed
xyz
x

Output
YES
NO
NO
YES
user: Phoenix has $n$ coins with weights $2^1, 2^2, \dots, 2^n$. He knows that $n$ is even.

He wants to split the coins into two piles such that each pile has exactly $\frac{n}{2}$ coins and the difference of weights between the two piles is minimized. Formally, let $a$ denote the sum of weights in the first pile, and $b$ denote the sum of weights in the second pile. Help Phoenix minimize $|a-b|$, the absolute value of $a-b$.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains an integer $n$ ($2 \le n \le 30$; $n$ is even) — the number of coins that Phoenix has. 


-----Output-----

For each test case, output one integer — the minimum possible difference of weights between the two piles.


-----Example-----
Input
2
2
4

Output
2
6



-----Note-----

In the first test case, Phoenix has two coins with weights $2$ and $4$. No matter how he divides the coins, the difference will be $4-2=2$.

In the second test case, Phoenix has four coins of weight $2$, $4$, $8$, and $16$. It is optimal for Phoenix to place coins with weights $2$ and $16$ in one pile, and coins with weights $4$ and $8$ in another pile. The difference is $(2+16)-(4+8)=6$.
user: Squirrel Liss loves nuts. There are n trees (numbered 1 to n from west to east) along a street and there is a delicious nut on the top of each tree. The height of the tree i is h_{i}. Liss wants to eat all nuts.

Now Liss is on the root of the tree with the number 1. In one second Liss can perform one of the following actions:  Walk up or down one unit on a tree.  Eat a nut on the top of the current tree.  Jump to the next tree. In this action the height of Liss doesn't change. More formally, when Liss is at height h of the tree i (1 ≤ i ≤ n - 1), she jumps to height h of the tree i + 1. This action can't be performed if h > h_{i} + 1. 

Compute the minimal time (in seconds) required to eat all nuts.


-----Input-----

The first line contains an integer n (1  ≤  n ≤ 10^5) — the number of trees.

Next n lines contains the height of trees: i-th line contains an integer h_{i} (1 ≤ h_{i} ≤ 10^4) — the height of the tree with the number i.


-----Output-----

Print a single integer — the minimal time required to eat all nuts in seconds.


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

Output
5

Input
5
2
1
2
1
1

Output
14
user: The Red Kingdom is attacked by the White King and the Black King!

The Kingdom is guarded by $n$ castles, the $i$-th castle is defended by $a_i$ soldiers. To conquer the Red Kingdom, the Kings have to eliminate all the defenders. 

Each day the White King launches an attack on one of the castles. Then, at night, the forces of the Black King attack a castle (possibly the same one). Then the White King attacks a castle, then the Black King, and so on. The first attack is performed by the White King.

Each attack must target a castle with at least one alive defender in it. There are three types of attacks:

  a mixed attack decreases the number of defenders in the targeted castle by $x$ (or sets it to $0$ if there are already less than $x$ defenders);  an infantry attack decreases the number of defenders in the targeted castle by $y$ (or sets it to $0$ if there are already less than $y$ defenders);  a cavalry attack decreases the number of defenders in the targeted castle by $z$ (or sets it to $0$ if there are already less than $z$ defenders). 

The mixed attack can be launched at any valid target (at any castle with at least one soldier). However, the infantry attack cannot be launched if the previous attack on the targeted castle had the same type, no matter when and by whom it was launched. The same applies to the cavalry attack. A castle that was not attacked at all can be targeted by any type of attack.

The King who launches the last attack will be glorified as the conqueror of the Red Kingdom, so both Kings want to launch the last attack (and they are wise enough to find a strategy that allows them to do it no matter what are the actions of their opponent, if such strategy exists). The White King is leading his first attack, and you are responsible for planning it. Can you calculate the number of possible options for the first attack that allow the White King to launch the last attack? Each option for the first attack is represented by the targeted castle and the type of attack, and two options are different if the targeted castles or the types of attack are different.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Then, the test cases follow. Each test case is represented by two lines. 

The first line contains four integers $n$, $x$, $y$ and $z$ ($1 \le n \le 3 \cdot 10^5$, $1 \le x, y, z \le 5$). 

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^{18}$).

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


-----Output-----

For each test case, print the answer to it: the number of possible options for the first attack of the White King (or $0$, if the Black King can launch the last attack no matter how the White King acts).


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

Output
2
3
0

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

Output
0
2
1
2
5
12
5
0
0
2
user: -----Input-----

The input contains a single integer $a$ ($0 \le a \le 63$).


-----Output-----

Output a single number.


-----Examples-----
Input
2

Output
2

Input
5

Output
24

Input
35

Output
50
user: There are two types of burgers in your restaurant — hamburgers and chicken burgers! To assemble a hamburger you need two buns and a beef patty. To assemble a chicken burger you need two buns and a chicken cutlet. 

You have $b$ buns, $p$ beef patties and $f$ chicken cutlets in your restaurant. You can sell one hamburger for $h$ dollars and one chicken burger for $c$ dollars. Calculate the maximum profit you can achieve.

You have to answer $t$ independent queries.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) – the number of queries.

The first line of each query contains three integers $b$, $p$ and $f$ ($1 \le b, ~p, ~f \le 100$) — the number of buns, beef patties and chicken cutlets in your restaurant.

The second line of each query contains two integers $h$ and $c$ ($1 \le h, ~c \le 100$) — the hamburger and chicken burger prices in your restaurant.


-----Output-----

For each query print one integer — the maximum profit you can achieve.


-----Example-----
Input
3
15 2 3
5 10
7 5 2
10 12
1 100 100
100 100

Output
40
34
0



-----Note-----

In first query you have to sell two hamburgers and three chicken burgers. Your income is $2 \cdot 5 + 3 \cdot 10 = 40$.

In second query you have to ell one hamburgers and two chicken burgers. Your income is $1 \cdot 10 + 2 \cdot 12 = 34$.

In third query you can not create any type of burgers because because you have only one bun. So your income is zero.
user: You are given two integers $n$ and $m$ ($m < n$). Consider a convex regular polygon of $n$ vertices. Recall that a regular polygon is a polygon that is equiangular (all angles are equal in measure) and equilateral (all sides have the same length). [Image] Examples of convex regular polygons 

Your task is to say if it is possible to build another convex regular polygon with $m$ vertices such that its center coincides with the center of the initial polygon and each of its vertices is some vertex of the initial polygon.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The next $t$ lines describe test cases. Each test case is given as two space-separated integers $n$ and $m$ ($3 \le m < n \le 100$) — the number of vertices in the initial polygon and the number of vertices in the polygon you want to build.


-----Output-----

For each test case, print the answer — "YES" (without quotes), if it is possible to build another convex regular polygon with $m$ vertices such that its center coincides with the center of the initial polygon and each of its vertices is some vertex of the initial polygon and "NO" otherwise.


-----Example-----
Input
2
6 3
7 3

Output
YES
NO



-----Note----- $0$ The first test case of the example 

It can be shown that the answer for the second test case of the example is "NO".
user: You are given an array consisting of $n$ integers $a_1$, $a_2$, ..., $a_n$. Initially $a_x = 1$, all other elements are equal to $0$.

You have to perform $m$ operations. During the $i$-th operation, you choose two indices $c$ and $d$ such that $l_i \le c, d \le r_i$, and swap $a_c$ and $a_d$.

Calculate the number of indices $k$ such that it is possible to choose the operations so that $a_k = 1$ in the end.


-----Input-----

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

The first line of each test case contains three integers $n$, $x$ and $m$ ($1 \le n \le 10^9$; $1 \le m \le 100$; $1 \le x \le n$).

Each of next $m$ lines contains the descriptions of the operations; the $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).


-----Output-----

For each test case print one integer — the number of indices $k$ such that it is possible to choose the operations so that $a_k = 1$ in the end.


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

Output
6
2
3



-----Note-----

In the first test case, it is possible to achieve $a_k = 1$ for every $k$. To do so, you may use the following operations:  swap $a_k$ and $a_4$;  swap $a_2$ and $a_2$;  swap $a_5$ and $a_5$. 

In the second test case, only $k = 1$ and $k = 2$ are possible answers. To achieve $a_1 = 1$, you have to swap $a_1$ and $a_1$ during the second operation. To achieve $a_2 = 1$, you have to swap $a_1$ and $a_2$ during the second operation.