meetforever/GRPO_CL huggingface dataset:
user: Hanh lives in a shared apartment. There are $n$ people (including Hanh) living there, each has a private fridge. 

$n$ fridges are secured by several steel chains. Each steel chain connects two different fridges and is protected by a digital lock. The owner of a fridge knows passcodes of all chains connected to it. A fridge can be open only if all chains connected to it are unlocked. For example, if a fridge has no chains connected to it at all, then any of $n$ people can open it.

 [Image] For exampe, in the picture there are $n=4$ people and $5$ chains. The first person knows passcodes of two chains: $1-4$ and $1-2$. The fridge $1$ can be open by its owner (the person $1$), also two people $2$ and $4$ (acting together) can open it. 

The weights of these fridges are $a_1, a_2, \ldots, a_n$. To make a steel chain connecting fridges $u$ and $v$, you have to pay $a_u + a_v$ dollars. Note that the landlord allows you to create multiple chains connecting the same pair of fridges. 

Hanh's apartment landlord asks you to create exactly $m$ steel chains so that all fridges are private. A fridge is private if and only if, among $n$ people living in the apartment, only the owner can open it (i.e. no other person acting alone can do it). In other words, the fridge $i$ is not private if there exists the person $j$ ($i \ne j$) that the person $j$ can open the fridge $i$.

For example, in the picture all the fridges are private. On the other hand, if there are $n=2$ fridges and only one chain (which connects them) then both fridges are not private (both fridges can be open not only by its owner but also by another person).

Of course, the landlord wants to minimize the total cost of all steel chains to fulfill his request. Determine whether there exists any way to make exactly $m$ chains, and if yes, output any solution that minimizes the total cost. 


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 10$). Then the descriptions of the test cases follow.

The first line of each test case contains two integers $n$, $m$ ($2 \le n \le 1000$, $1 \le m \le n$) — the number of people living in Hanh's apartment and the number of steel chains that the landlord requires, respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^4$) — weights of all fridges.


-----Output-----

For each test case:

  If there is no solution, print a single integer $-1$.  Otherwise, print a single integer $c$ — the minimum total cost. The $i$-th of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), meaning that the $i$-th steel chain connects fridges $u_i$ and $v_i$. An arbitrary number of chains can be between a pair of fridges. 

If there are multiple answers, print any.


-----Example-----
Input
3
4 4
1 1 1 1
3 1
1 2 3
3 3
1 2 3

Output
8
1 2
4 3
3 2
4 1
-1
12
3 2
1 2
3 1
user: Consider the set of all nonnegative integers: ${0, 1, 2, \dots}$. Given two integers $a$ and $b$ ($1 \le a, b \le 10^4$). We paint all the numbers in increasing number first we paint $0$, then we paint $1$, then $2$ and so on.

Each number is painted white or black. We paint a number $i$ according to the following rules:   if $i = 0$, it is colored white;   if $i \ge a$ and $i - a$ is colored white, $i$ is also colored white;   if $i \ge b$ and $i - b$ is colored white, $i$ is also colored white;   if $i$ is still not colored white, it is colored black. 

In this way, each nonnegative integer gets one of two colors.

For example, if $a=3$, $b=5$, then the colors of the numbers (in the order from $0$) are: white ($0$), black ($1$), black ($2$), white ($3$), black ($4$), white ($5$), white ($6$), black ($7$), white ($8$), white ($9$), ...

Note that:   It is possible that there are infinitely many nonnegative integers colored black. For example, if $a = 10$ and $b = 10$, then only $0, 10, 20, 30$ and any other nonnegative integers that end in $0$ when written in base 10 are white. The other integers are colored black.   It is also possible that there are only finitely many nonnegative integers colored black. For example, when $a = 1$ and $b = 10$, then there is no nonnegative integer colored black at all. 

Your task is to determine whether or not the number of nonnegative integers colored black is infinite.

If there are infinitely many nonnegative integers colored black, simply print a line containing "Infinite" (without the quotes). Otherwise, print "Finite" (without the quotes).


-----Input-----

The first line of input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases in the input. Then $t$ lines follow, each line contains two space-separated integers $a$ and $b$ ($1 \le a, b \le 10^4$).


-----Output-----

For each test case, print one line containing either "Infinite" or "Finite" (without the quotes). Output is case-insensitive (i.e. "infinite", "inFiNite" or "finiTE" are all valid answers).


-----Example-----
Input
4
10 10
1 10
6 9
7 3

Output
Infinite
Finite
Infinite
Finite
user: Mahmoud wants to send a message to his friend Ehab. Their language consists of n words numbered from 1 to n. Some words have the same meaning so there are k groups of words such that all the words in some group have the same meaning.

Mahmoud knows that the i-th word can be sent with cost a_{i}. For each word in his message, Mahmoud can either replace it with another word of the same meaning or leave it as it is. Can you help Mahmoud determine the minimum cost of sending the message?

The cost of sending the message is the sum of the costs of sending every word in it.


-----Input-----

The first line of input contains integers n, k and m (1 ≤ k ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5) — the number of words in their language, the number of groups of words, and the number of words in Mahmoud's message respectively.

The second line contains n strings consisting of lowercase English letters of length not exceeding 20 which represent the words. It's guaranteed that the words are distinct.

The third line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) where a_{i} is the cost of sending the i-th word.

The next k lines describe the groups of words of same meaning. The next k lines each start with an integer x (1 ≤ x ≤ n) which means that there are x words in this group, followed by x integers which represent the indices of words in this group. It's guaranteed that each word appears in exactly one group.

The next line contains m space-separated words which represent Mahmoud's message. Each of these words appears in the list of language's words.


-----Output-----

The only line should contain the minimum cost to send the message after replacing some words (maybe none) with some words of the same meaning.


-----Examples-----
Input
5 4 4
i loser am the second
100 1 1 5 10
1 1
1 3
2 2 5
1 4
i am the second

Output
107
Input
5 4 4
i loser am the second
100 20 1 5 10
1 1
1 3
2 2 5
1 4
i am the second

Output
116


-----Note-----

In the first sample, Mahmoud should replace the word "second" with the word "loser" because it has less cost so the cost will be 100+1+5+1=107.

In the second sample, Mahmoud shouldn't do any replacement so the cost will be 100+1+5+10=116.
user: You have an array $a_1, a_2, \dots, a_n$. 

Let's call some subarray $a_l, a_{l + 1}, \dots , a_r$ of this array a subpermutation if it contains all integers from $1$ to $r-l+1$ exactly once. For example, array $a = [2, 2, 1, 3, 2, 3, 1]$ contains $6$ subarrays which are subpermutations: $[a_2 \dots a_3]$, $[a_2 \dots a_4]$, $[a_3 \dots a_3]$, $[a_3 \dots a_5]$, $[a_5 \dots a_7]$, $[a_7 \dots a_7]$.

You are asked to calculate the number of subpermutations.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le n$). 

This array can contain the same integers.


-----Output-----

Print the number of subpermutations of the array $a$.


-----Examples-----
Input
8
2 4 1 3 4 2 1 2

Output
7

Input
5
1 1 2 1 2

Output
6



-----Note-----

There are $7$ subpermutations in the first test case. Their segments of indices are $[1, 4]$, $[3, 3]$, $[3, 6]$, $[4, 7]$, $[6, 7]$, $[7, 7]$ and $[7, 8]$.

In the second test case $6$ subpermutations exist: $[1, 1]$, $[2, 2]$, $[2, 3]$, $[3, 4]$, $[4, 4]$ and $[4, 5]$.
user: After finding and moving to the new planet that supports human life, discussions started on which currency should be used. After long negotiations, Bitcoin was ultimately chosen as the universal currency.

These were the great news for Alice, whose grandfather got into Bitcoin mining in 2013, and accumulated a lot of them throughout the years. Unfortunately, when paying something in bitcoin everyone can see how many bitcoins you have in your public address wallet. 

This worried Alice, so she decided to split her bitcoins among multiple different addresses, so that every address has at most $x$ satoshi (1 bitcoin = $10^8$ satoshi). She can create new public address wallets for free and is willing to pay $f$ fee in satoshi per transaction to ensure acceptable speed of transfer. The fee is deducted from the address the transaction was sent from. Tell Alice how much total fee in satoshi she will need to pay to achieve her goal.


-----Input-----

First line contains number $N$ ($1 \leq N \leq 200\,000$) representing total number of public addresses Alice has.

Next line contains $N$ integer numbers $a_i$ ($1 \leq a_i \leq 10^9$) separated by a single space, representing how many satoshi Alice has in her public addresses.

Last line contains two numbers $x$, $f$ ($1 \leq f < x \leq 10^9$) representing maximum number of satoshies Alice can have in one address, as well as fee in satoshies she is willing to pay per transaction. 


-----Output-----

Output one integer number representing total fee in satoshi Alice will need to pay to achieve her goal.


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

Output
4



-----Note-----

Alice can make two transactions in a following way:

0. 13 7 6 (initial state)

1. 6 7 6 5 (create new address and transfer from first public address 5 satoshies)

2. 6 4 6 5 1 (create new address and transfer from second address 1 satoshi)

Since cost per transaction is 2 satoshies, total fee is 4.
user: Roy and Biv have a set of n points on the infinite number line.

Each point has one of 3 colors: red, green, or blue.

Roy and Biv would like to connect all the points with some edges. Edges can be drawn between any of the two of the given points. The cost of an edge is equal to the distance between the two points it connects.

They want to do this in such a way that they will both see that all the points are connected (either directly or indirectly).

However, there is a catch: Roy cannot see the color red and Biv cannot see the color blue.

Therefore, they have to choose the edges in such a way that if all the red points are removed, the remaining blue and green points are connected (and similarly, if all the blue points are removed, the remaining red and green points are connected).

Help them compute the minimum cost way to choose edges to satisfy the above constraints.


-----Input-----

The first line will contain an integer n (1 ≤ n ≤ 300 000), the number of points.

The next n lines will contain two tokens p_{i} and c_{i} (p_{i} is an integer, 1 ≤ p_{i} ≤ 10^9, c_{i} is a uppercase English letter 'R', 'G' or 'B'), denoting the position of the i-th point and the color of the i-th point. 'R' means red, 'G' denotes green, and 'B' means blue. The positions will be in strictly increasing order.


-----Output-----

Print a single integer, the minimum cost way to solve the problem.


-----Examples-----
Input
4
1 G
5 R
10 B
15 G

Output
23

Input
4
1 G
2 R
3 B
10 G

Output
12



-----Note-----

In the first sample, it is optimal to draw edges between the points (1,2), (1,4), (3,4). These have costs 4, 14, 5, respectively.
user: George decided to prepare a Codesecrof round, so he has prepared m problems for the round. Let's number the problems with integers 1 through m. George estimates the i-th problem's complexity by integer b_{i}.

To make the round good, he needs to put at least n problems there. Besides, he needs to have at least one problem with complexity exactly a_1, at least one with complexity exactly a_2, ..., and at least one with complexity exactly a_{n}. Of course, the round can also have problems with other complexities.

George has a poor imagination. It's easier for him to make some already prepared problem simpler than to come up with a new one and prepare it. George is magnificent at simplifying problems. He can simplify any already prepared problem with complexity c to any positive integer complexity d (c ≥ d), by changing limits on the input data.

However, nothing is so simple. George understood that even if he simplifies some problems, he can run out of problems for a good round. That's why he decided to find out the minimum number of problems he needs to come up with in addition to the m he's prepared in order to make a good round. Note that George can come up with a new problem of any complexity.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 3000) — the minimal number of problems in a good round and the number of problems George's prepared. The second line contains space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_1 < a_2 < ... < a_{n} ≤ 10^6) — the requirements for the complexity of the problems in a good round. The third line contains space-separated integers b_1, b_2, ..., b_{m} (1 ≤ b_1 ≤ b_2... ≤ b_{m} ≤ 10^6) — the complexities of the problems prepared by George. 


-----Output-----

Print a single integer — the answer to the problem.


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

Output
0

Input
3 5
1 2 3
1 1 1 1 1

Output
2

Input
3 1
2 3 4
1

Output
3



-----Note-----

In the first sample the set of the prepared problems meets the requirements for a good round.

In the second sample, it is enough to come up with and prepare two problems with complexities 2 and 3 to get a good round.

In the third sample it is very easy to get a good round if come up with and prepare extra problems with complexities: 2, 3, 4.
user: You've got a robot, its task is destroying bombs on a square plane. Specifically, the square plane contains n bombs, the i-th bomb is at point with coordinates (x_{i}, y_{i}). We know that no two bombs are at the same point and that no bomb is at point with coordinates (0, 0). Initially, the robot is at point with coordinates (0, 0). Also, let's mark the robot's current position as (x, y). In order to destroy all the bombs, the robot can perform three types of operations:  Operation has format "1 k dir". To perform the operation robot have to move in direction dir k (k ≥ 1) times. There are only 4 directions the robot can move in: "R", "L", "U", "D". During one move the robot can move from the current point to one of following points: (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1) (corresponding to directions). It is forbidden to move from point (x, y), if at least one point on the path (besides the destination point) contains a bomb.  Operation has format "2". To perform the operation robot have to pick a bomb at point (x, y) and put it in a special container. Thus, the robot can carry the bomb from any point to any other point. The operation cannot be performed if point (x, y) has no bomb. It is forbidden to pick a bomb if the robot already has a bomb in its container.  Operation has format "3". To perform the operation robot have to take a bomb out of the container and destroy it. You are allowed to perform this operation only if the robot is at point (0, 0). It is forbidden to perform the operation if the container has no bomb. 

Help the robot and find the shortest possible sequence of operations he can perform to destroy all bombs on the coordinate plane.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of bombs on the coordinate plane. Next n lines contain two integers each. The i-th line contains numbers (x_{i}, y_{i}) ( - 10^9 ≤ x_{i}, y_{i} ≤ 10^9) — the coordinates of the i-th bomb. It is guaranteed that no two bombs are located at the same point and no bomb is at point (0, 0). 


-----Output-----

In a single line print a single integer k — the minimum number of operations needed to destroy all bombs. On the next lines print the descriptions of these k operations. If there are multiple sequences, you can print any of them. It is guaranteed that there is the solution where k ≤ 10^6.


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

Output
12
1 1 R
1 1 U
2
1 1 L
1 1 D
3
1 1 L
1 1 D
2
1 1 R
1 1 U
3

Input
3
5 0
0 5
1 0

Output
12
1 1 R
2
1 1 L
3
1 5 R
2
1 5 L
3
1 5 U
2
1 5 D
3
user: Alexander is a well-known programmer. Today he decided to finally go out and play football, but with the first hit he left a dent on the new Rolls-Royce of the wealthy businessman Big Vova. Vladimir has recently opened a store on the popular online marketplace "Zmey-Gorynych", and offers Alex a job: if he shows his programming skills by solving a task, he'll work as a cybersecurity specialist. Otherwise, he'll be delivering some doubtful products for the next two years.

You're given $n$ positive integers $a_1, a_2, \dots, a_n$. Using each of them exactly at once, you're to make such sequence $b_1, b_2, \dots, b_n$ that sequence $c_1, c_2, \dots, c_n$ is lexicographically maximal, where $c_i=GCD(b_1,\dots,b_i)$ - the greatest common divisor of the first $i$ elements of $b$. 

Alexander is really afraid of the conditions of this simple task, so he asks you to solve it.

A sequence $a$ is lexicographically smaller than a sequence $b$ if and only if one of the following holds:



 $a$ is a prefix of $b$, but $a \ne b$;

 in the first position where $a$ and $b$ differ, the sequence $a$ has a smaller element than the corresponding element in $b$.


-----Input-----

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

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^3$)  — the length of the sequence $a$.

The second line of each test case contains $n$ integers $a_1,\dots,a_n$ ($1 \le a_i \le 10^3$)  — the sequence $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^3$.


-----Output-----

For each test case output the answer in a single line  — the desired sequence $b$. If there are multiple answers, print any.


-----Example-----
Input
7
2
2 5
4
1 8 2 3
3
3 8 9
5
64 25 75 100 50
1
42
6
96 128 88 80 52 7
5
2 4 8 16 17

Output
5 2 
8 2 1 3 
9 3 8 
100 50 25 75 64 
42 
128 96 80 88 52 7 
17 2 4 8 16 



-----Note-----

In the first test case of the example, there are only two possible permutations $b$  — $[2, 5]$ and $[5, 2]$: for the first one $c=[2, 1]$, for the second one $c=[5, 1]$.

In the third test case of the example, number $9$ should be the first in $b$, and $GCD(9, 3)=3$, $GCD(9, 8)=1$, so the second number of $b$ should be $3$.

In the seventh test case of the example, first four numbers pairwise have a common divisor (a power of two), but none of them can be the first in the optimal permutation $b$.
user: You are playing a game where your character should overcome different obstacles. The current problem is to come down from a cliff. The cliff has height $h$, and there is a moving platform on each height $x$ from $1$ to $h$.

Each platform is either hidden inside the cliff or moved out. At first, there are $n$ moved out platforms on heights $p_1, p_2, \dots, p_n$. The platform on height $h$ is moved out (and the character is initially standing there).

If you character is standing on some moved out platform on height $x$, then he can pull a special lever, which switches the state of two platforms: on height $x$ and $x - 1$. In other words, the platform you are currently standing on will hide in the cliff and the platform one unit below will change it state: it will hide if it was moved out or move out if it was hidden. In the second case, you will safely land on it. Note that this is the only way to move from one platform to another.

Your character is quite fragile, so it can safely fall from the height no more than $2$. In other words falling from the platform $x$ to platform $x - 2$ is okay, but falling from $x$ to $x - 3$ (or lower) is certain death. 

Sometimes it's not possible to come down from the cliff, but you can always buy (for donate currency) several magic crystals. Each magic crystal can be used to change the state of any single platform (except platform on height $h$, which is unaffected by the crystals). After being used, the crystal disappears.

What is the minimum number of magic crystal you need to buy to safely land on the $0$ ground level?


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 100$) — the number of queries. Each query contains two lines and is independent of all other queries.

The first line of each query contains two integers $h$ and $n$ ($1 \le h \le 10^9$, $1 \le n \le \min(h, 2 \cdot 10^5)$) — the height of the cliff and the number of moved out platforms.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($h = p_1 > p_2 > \dots > p_n \ge 1$) — the corresponding moved out platforms in the descending order of their heights.

The sum of $n$ over all queries does not exceed $2 \cdot 10^5$.


-----Output-----

For each query print one integer — the minimum number of magic crystals you have to spend to safely come down on the ground level (with height $0$).


-----Example-----
Input
4
3 2
3 1
8 6
8 7 6 5 3 2
9 6
9 8 5 4 3 1
1 1
1

Output
0
1
2
0
user: Carousel Boutique is busy again! Rarity has decided to visit the pony ball and she surely needs a new dress, because going out in the same dress several times is a sign of bad manners. First of all, she needs a dress pattern, which she is going to cut out from the rectangular piece of the multicolored fabric.

The piece of the multicolored fabric consists of $n \times m$ separate square scraps. Since Rarity likes dresses in style, a dress pattern must only include scraps sharing the same color. A dress pattern must be the square, and since Rarity is fond of rhombuses, the sides of a pattern must form a $45^{\circ}$ angle with sides of a piece of fabric (that way it will be resembling the traditional picture of a rhombus).

Examples of proper dress patterns: [Image] Examples of improper dress patterns: [Image] The first one consists of multi-colored scraps, the second one goes beyond the bounds of the piece of fabric, the third one is not a square with sides forming a $45^{\circ}$ angle with sides of the piece of fabric.

Rarity wonders how many ways to cut out a dress pattern that satisfies all the conditions that do exist. Please help her and satisfy her curiosity so she can continue working on her new masterpiece!


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2000$). Each of the next $n$ lines contains $m$ characters: lowercase English letters, the $j$-th of which corresponds to scrap in the current line and in the $j$-th column. Scraps having the same letter share the same color, scraps having different letters have different colors.


-----Output-----

Print a single integer: the number of ways to cut out a dress pattern to satisfy all of Rarity's conditions.


-----Examples-----
Input
3 3
aaa
aaa
aaa

Output
10

Input
3 4
abab
baba
abab

Output
12

Input
5 5
zbacg
baaac
aaaaa
eaaad
weadd

Output
31



-----Note-----

In the first example, all the dress patterns of size $1$ and one of size $2$ are satisfactory.

In the second example, only the dress patterns of size $1$ are satisfactory.