meetforever/GRPO_CL huggingface dataset:
user: Ilya is very fond of graphs, especially trees. During his last trip to the forest Ilya found a very interesting tree rooted at vertex 1. There is an integer number written on each vertex of the tree; the number written on vertex i is equal to a_{i}.

Ilya believes that the beauty of the vertex x is the greatest common divisor of all numbers written on the vertices on the path from the root to x, including this vertex itself. In addition, Ilya can change the number in one arbitrary vertex to 0 or leave all vertices unchanged. Now for each vertex Ilya wants to know the maximum possible beauty it can have.

For each vertex the answer must be considered independently.

The beauty of the root equals to number written on it.


-----Input-----

First line contains one integer number n — the number of vertices in tree (1 ≤ n ≤ 2·10^5).

Next line contains n integer numbers a_{i} (1 ≤ i ≤ n, 1 ≤ a_{i} ≤ 2·10^5).

Each of next n - 1 lines contains two integer numbers x and y (1 ≤ x, y ≤ n, x ≠ y), which means that there is an edge (x, y) in the tree.


-----Output-----

Output n numbers separated by spaces, where i-th number equals to maximum possible beauty of vertex i.


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

Output
6 6 

Input
3
6 2 3
1 2
1 3

Output
6 6 6 

Input
1
10

Output
10
user: Despite his bad reputation, Captain Flint is a friendly person (at least, friendly to animals). Now Captain Flint is searching worthy sailors to join his new crew (solely for peaceful purposes). A sailor is considered as worthy if he can solve Flint's task.

Recently, out of blue Captain Flint has been interested in math and even defined a new class of integers. Let's define a positive integer $x$ as nearly prime if it can be represented as $p \cdot q$, where $1 < p < q$ and $p$ and $q$ are prime numbers. For example, integers $6$ and $10$ are nearly primes (since $2 \cdot 3 = 6$ and $2 \cdot 5 = 10$), but integers $1$, $3$, $4$, $16$, $17$ or $44$ are not.

Captain Flint guessed an integer $n$ and asked you: can you represent it as the sum of $4$ different positive integers where at least $3$ of them should be nearly prime.

Uncle Bogdan easily solved the task and joined the crew. Can you do the same?


-----Input-----

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

Next $t$ lines contain test cases — one per line. The first and only line of each test case contains the single integer $n$ $(1 \le n \le 2 \cdot 10^5)$ — the number Flint guessed.


-----Output-----

For each test case print:   YES and $4$ different positive integers such that at least $3$ of them are nearly prime and their sum is equal to $n$ (if there are multiple answers print any of them);  NO if there is no way to represent $n$ as the sum of $4$ different positive integers where at least $3$ of them are nearly prime.  You can print each character of YES or NO in any case.


-----Example-----
Input
7
7
23
31
36
44
100
258

Output
NO
NO
YES
14 10 6 1
YES
5 6 10 15
YES
6 7 10 21
YES
2 10 33 55
YES
10 21 221 6


-----Note-----

In the first and second test cases, it can be proven that there are no four different positive integers such that at least three of them are nearly prime.

In the third test case, $n=31=2 \cdot 7 + 2 \cdot 5 + 2 \cdot 3 + 1$: integers $14$, $10$, $6$ are nearly prime.

In the fourth test case, $n=36=5 + 2 \cdot 3 + 2 \cdot 5 + 3 \cdot 5$: integers $6$, $10$, $15$ are nearly prime.

In the fifth test case, $n=44=2 \cdot 3 + 7 + 2 \cdot 5 + 3 \cdot 7$: integers $6$, $10$, $21$ are nearly prime.

In the sixth test case, $n=100=2 + 2 \cdot 5 + 3 \cdot 11 + 5 \cdot 11$: integers $10$, $33$, $55$ are nearly prime.

In the seventh test case, $n=258=2 \cdot 5 + 3 \cdot 7 + 13 \cdot 17 + 2 \cdot 3$: integers $10$, $21$, $221$, $6$ are nearly prime.
user: This is the easy version of the problem. The difference between the versions is that in the easy version all prices $a_i$ are different. You can make hacks if and only if you solved both versions of the problem.

Today is Sage's birthday, and she will go shopping to buy ice spheres. All $n$ ice spheres are placed in a row and they are numbered from $1$ to $n$ from left to right. Each ice sphere has a positive integer price. In this version all prices are different.

An ice sphere is cheap if it costs strictly less than two neighboring ice spheres: the nearest to the left and the nearest to the right. The leftmost and the rightmost ice spheres are not cheap. Sage will choose all cheap ice spheres and then buy only them.

You can visit the shop before Sage and reorder the ice spheres as you wish. Find out the maximum number of ice spheres that Sage can buy, and show how the ice spheres should be reordered.


-----Input-----

The first line contains a single integer $n$ $(1 \le n \le 10^5)$ — the number of ice spheres in the shop.

The second line contains $n$ different integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$ — the prices of ice spheres.


-----Output-----

In the first line print the maximum number of ice spheres that Sage can buy.

In the second line print the prices of ice spheres in the optimal order. If there are several correct answers, you can print any of them.


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

Output
2
3 1 4 2 5 


-----Note-----

In the example it's not possible to place ice spheres in any order so that Sage would buy $3$ of them. If the ice spheres are placed like this $(3, 1, 4, 2, 5)$, then Sage will buy two spheres: one for $1$ and one for $2$, because they are cheap.
user: You are given a tree (an undirected connected acyclic graph) consisting of $n$ vertices and $n - 1$ edges. A number is written on each edge, each number is either $0$ (let's call such edges $0$-edges) or $1$ (those are $1$-edges).

Let's call an ordered pair of vertices $(x, y)$ ($x \ne y$) valid if, while traversing the simple path from $x$ to $y$, we never go through a $0$-edge after going through a $1$-edge. Your task is to calculate the number of valid pairs in the tree.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 200000$) — the number of vertices in the tree.

Then $n - 1$ lines follow, each denoting an edge of the tree. Each edge is represented by three integers $x_i$, $y_i$ and $c_i$ ($1 \le x_i, y_i \le n$, $0 \le c_i \le 1$, $x_i \ne y_i$) — the vertices connected by this edge and the number written on it, respectively.

It is guaranteed that the given edges form a tree.


-----Output-----

Print one integer — the number of valid pairs of vertices.


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

Output
34



-----Note-----

The picture corresponding to the first example:

[Image]
user: You are given an angle $\text{ang}$. 

The Jury asks You to find such regular $n$-gon (regular polygon with $n$ vertices) that it has three vertices $a$, $b$ and $c$ (they can be non-consecutive) with $\angle{abc} = \text{ang}$ or report that there is no such $n$-gon. [Image] 

If there are several answers, print the minimal one. It is guarantied that if answer exists then it doesn't exceed $998244353$.


-----Input-----

The first line contains single integer $T$ ($1 \le T \le 180$) — the number of queries. 

Each of the next $T$ lines contains one integer $\text{ang}$ ($1 \le \text{ang} < 180$) — the angle measured in degrees. 


-----Output-----

For each query print single integer $n$ ($3 \le n \le 998244353$) — minimal possible number of vertices in the regular $n$-gon or $-1$ if there is no such $n$.


-----Example-----
Input
4
54
50
2
178

Output
10
18
90
180



-----Note-----

The answer for the first query is on the picture above.

The answer for the second query is reached on a regular $18$-gon. For example, $\angle{v_2 v_1 v_6} = 50^{\circ}$.

The example angle for the third query is $\angle{v_{11} v_{10} v_{12}} = 2^{\circ}$.

In the fourth query, minimal possible $n$ is $180$ (not $90$).
user: Given a collection of distinct integers, return all possible permutations.

Example:


Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Answer: {"fn_name": "permute", "inputs": [[[1,2,3]], [[0,1]], [[1]]], "outputs": [[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]], [[0,1],[1,0]], [[1]]]}
user: Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:


       All numbers will be positive integers.
       The solution set must not contain duplicate combinations.


Example 1:


Input: k = 3, n = 7
Output: [[1,2,4]]


Example 2:


Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

Answer: {"fn_name": "combinationSum3", "inputs": [[3,7], [3, 9], [9, 45]], "outputs": [[[1,2,4]], [[1,2,6],[1,3,5],[2,3,4]], [[1,2,3,4,5,6,7,8,9]]]}
user: Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
 
Example 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:
Input: s = ""
Output: 0

 
Constraints:

0 <= s.length <= 3 * 104
s[i] is '(', or ')'.

Answer: {"fn_name": "longestValidParentheses", "inputs": [["\"(()\""], ["\")()())\""], ["\"\""]], "outputs": [2, 4, 0]}
user: Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:


Input: [3,2,3]
Output: [3]

Example 2:


Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Answer: {"fn_name": "majorityElement", "inputs": [[[3,2,3]], [[1]], [[1,2]]], "outputs": [[3], [1], [1,2]]}
user: Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.
In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].
If there is no way to make arr1 strictly increasing, return -1.
 
Example 1:
Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:
Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].

Example 3:
Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.
 
Constraints:

1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

Answer: {"fn_name": "makeArrayIncreasing", "inputs": [[[1, 5, 3, 6, 7], [1, 3, 2, 4]], [[1,5,3,6,7], [4,3,1]], [[1,5,3,6,7], [1,6,3,3]]], "outputs": [1,2,-1]}
user: We have a grid with H rows and W columns. At first, all cells were painted white.
Snuke painted N of these cells. The i-th ( 1 \leq i \leq N ) cell he painted is the cell at the a_i-th row and b_i-th column.
Compute the following:
 - For each integer j ( 0 \leq j \leq 9 ), how many subrectangles of size 3×3 of the grid contains exactly j black cells, after Snuke painted N cells?

-----Constraints-----
 - 3 \leq H \leq 10^9
 - 3 \leq W \leq 10^9
 - 0 \leq N \leq min(10^5,H×W)
 - 1 \leq a_i \leq H (1 \leq i \leq N)
 - 1 \leq b_i \leq W (1 \leq i \leq N)
 - (a_i, b_i) \neq (a_j, b_j) (i \neq j)

-----Input-----
The input is given from Standard Input in the following format:
H W N
a_1 b_1
:
a_N b_N

-----Output-----
Print 10 lines.
The (j+1)-th ( 0 \leq j \leq 9 ) line should contain the number of the subrectangles of size 3×3 of the grid that contains exactly j black cells.

-----Sample Input-----
4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4

-----Sample Output-----
0
0
0
2
4
0
0
0
0
0


There are six subrectangles of size 3×3. Two of them contain three black cells each, and the remaining four contain four black cells each.
user: Kizahashi, who was appointed as the administrator of ABC at National Problem Workshop in the Kingdom of AtCoder, got too excited and took on too many jobs.
Let the current time be time 0. Kizahashi has N jobs numbered 1 to N.
It takes A_i units of time for Kizahashi to complete Job i. The deadline for Job i is time B_i, and he must complete the job before or at this time.
Kizahashi cannot work on two or more jobs simultaneously, but when he completes a job, he can start working on another immediately.
Can Kizahashi complete all the jobs in time? If he can, print Yes; if he cannot, print No.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2 \times 10^5
 - 1 \leq A_i, B_i \leq 10^9 (1 \leq i \leq N)

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 B_1
.
.
.
A_N B_N

-----Output-----
If Kizahashi can complete all the jobs in time, print Yes; if he cannot, print No.

-----Sample Input-----
5
2 4
1 9
1 8
4 9
3 12

-----Sample Output-----
Yes

He can complete all the jobs in time by, for example, doing them in the following order:
 - Do Job 2 from time 0 to 1.
 - Do Job 1 from time 1 to 3.
 - Do Job 4 from time 3 to 7.
 - Do Job 3 from time 7 to 8.
 - Do Job 5 from time 8 to 11.
Note that it is fine to complete Job 3 exactly at the deadline, time 8.
user: We have N points in a two-dimensional plane.

The coordinates of the i-th point (1 \leq i \leq N) are (x_i,y_i).

Let us consider a rectangle whose sides are parallel to the coordinate axes that contains K or more of the N points in its interior.

Here, points on the sides of the rectangle are considered to be in the interior.

Find the minimum possible area of such a rectangle.  

-----Constraints-----
 - 2 \leq K \leq N \leq 50 
 - -10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N) 
 - x_i≠x_j (1 \leq i<j \leq N) 
 - y_i≠y_j (1 \leq i<j \leq N) 
 - All input values are integers. (Added at 21:50 JST)  

-----Input-----
Input is given from Standard Input in the following format:  
N K  
x_1 y_1
:  
x_{N} y_{N}

-----Output-----
Print the minimum possible area of a rectangle that satisfies the condition.  

-----Sample Input-----
4 4
1 4
3 3
6 2
8 1

-----Sample Output-----
21

One rectangle that satisfies the condition with the minimum possible area has the following vertices: (1,1), (8,1), (1,4) and (8,4).

Its area is (8-1) × (4-1) = 21.
user: For two sequences S and T of length N consisting of 0 and 1, let us define f(S, T) as follows:
 - Consider repeating the following operation on S so that S will be equal to T. f(S, T) is the minimum possible total cost of those operations.
 - Change S_i (from 0 to 1 or vice versa). The cost of this operation is D \times C_i, where D is the number of integers j such that S_j \neq T_j (1 \leq j \leq N) just before this change.
There are 2^N \times (2^N - 1) pairs (S, T) of different sequences of length N consisting of 0 and 1. Compute the sum of f(S, T) over all of those pairs, modulo (10^9+7).

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - 1 \leq C_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
C_1 C_2 \cdots C_N

-----Output-----
Print the sum of f(S, T), modulo (10^9+7).

-----Sample Input-----
1
1000000000

-----Sample Output-----
999999993

There are two pairs (S, T) of different sequences of length 2 consisting of 0 and 1, as follows:
 - S = (0), T = (1): by changing S_1 to 1, we can have S = T at the cost of 1000000000, so f(S, T) = 1000000000.
 - S = (1), T = (0): by changing S_1 to 0, we can have S = T at the cost of 1000000000, so f(S, T) = 1000000000.
The sum of these is 2000000000, and we should print it modulo (10^9+7), that is, 999999993.
user: There is an infinitely large pond, which we consider as a number line.
In this pond, there are N lotuses floating at coordinates 0, 1, 2, ..., N-2 and N-1.
On the lotus at coordinate i, an integer s_i is written.
You are standing on the lotus at coordinate 0. You will play a game that proceeds as follows:
 - 1. Choose positive integers A and B. Your score is initially 0.
 - 2. Let x be your current coordinate, and y = x+A. The lotus at coordinate x disappears, and you move to coordinate y.
 - If y = N-1, the game ends.
 - If y \neq N-1 and there is a lotus floating at coordinate y, your score increases by s_y.
 - If y \neq N-1 and there is no lotus floating at coordinate y, you drown. Your score decreases by 10^{100} points, and the game ends.
 - 3. Let x be your current coordinate, and y = x-B. The lotus at coordinate x disappears, and you move to coordinate y.
 - If y = N-1, the game ends.
 - If y \neq N-1 and there is a lotus floating at coordinate y, your score increases by s_y.
 - If y \neq N-1 and there is no lotus floating at coordinate y, you drown. Your score decreases by 10^{100} points, and the game ends.
 - 4. Go back to step 2.
You want to end the game with as high a score as possible.
What is the score obtained by the optimal choice of A and B?

-----Constraints-----
 - 3 \leq N \leq 10^5
 - -10^9 \leq s_i \leq 10^9
 - s_0=s_{N-1}=0
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
s_0 s_1 ...... s_{N-1}

-----Output-----
Print the score obtained by the optimal choice of A and B.

-----Sample Input-----
5
0 2 5 1 0

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

If you choose A = 3 and B = 2, the game proceeds as follows:
 - Move to coordinate 0 + 3 = 3. Your score increases by s_3 = 1.
 - Move to coordinate 3 - 2 = 1. Your score increases by s_1 = 2.
 - Move to coordinate 1 + 3 = 4. The game ends with a score of 3.
There is no way to end the game with a score of 4 or higher, so the answer is 3. Note that you cannot land the lotus at coordinate 2 without drowning later.
user: Takahashi has N cards. The i-th of these cards has an integer A_i written on it.
Takahashi will choose an integer K, and then repeat the following operation some number of times:
 - Choose exactly K cards such that the integers written on them are all different, and eat those cards. (The eaten cards disappear.)
For each K = 1,2, \ldots, N, find the maximum number of times Takahashi can do the operation.

-----Constraints-----
 -  1 \le N \le 3 \times 10^5 
 -  1 \le A_i \le N 
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_N

-----Output-----
Print N integers.
The t-th (1 \le t \le N) of them should be the answer for the case K=t.

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

-----Sample Output-----
3
1
0

For K = 1, we can do the operation as follows:
 - Choose the first card to eat.
 - Choose the second card to eat.
 - Choose the third card to eat.
For K = 2, we can do the operation as follows:
 - Choose the first and second cards to eat.
For K = 3, we cannot do the operation at all. Note that we cannot choose the first and third cards at the same time.
user: We have N logs of lengths A_1,A_2,\cdots A_N.
We can cut these logs at most K times in total. When a log of length L is cut at a point whose distance from an end of the log is t (0<t<L), it becomes two logs of lengths t and L-t.
Find the shortest possible length of the longest log after at most K cuts, and print it after rounding up to an integer.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - 0 \leq K \leq 10^9
 - 1 \leq A_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 A_2 \cdots A_N

-----Output-----
Print an integer representing the answer.

-----Sample Input-----
2 3
7 9

-----Sample Output-----
4

 - First, we will cut the log of length 7 at a point whose distance from an end of the log is 3.5, resulting in two logs of length 3.5 each.
 - Next, we will cut the log of length 9 at a point whose distance from an end of the log is 3, resulting in two logs of length 3 and 6.
 - Lastly, we will cut the log of length 6 at a point whose distance from an end of the log is 3.3, resulting in two logs of length 3.3 and 2.7.
In this case, the longest length of a log will be 3.5, which is the shortest possible result. After rounding up to an integer, the output should be 4.
user: You are given a string S of length N consisting of ( and ). Your task is to insert some number of ( and ) into S to obtain a correct bracket sequence.

Here, a correct bracket sequence is defined as follows:  
 - () is a correct bracket sequence.
 - If X is a correct bracket sequence, the concatenation of (, X and ) in this order is also a correct bracket sequence.
 - If X and Y are correct bracket sequences, the concatenation of X and Y in this order is also a correct bracket sequence.
 - Every correct bracket sequence can be derived from the rules above.
Find the shortest correct bracket sequence that can be obtained. If there is more than one such sequence, find the lexicographically smallest one.

-----Constraints-----
 - The length of S is N.
 - 1 ≤ N ≤ 100
 - S consists of ( and ).

-----Input-----
Input is given from Standard Input in the following format:
N
S

-----Output-----
Print the lexicographically smallest string among the shortest correct bracket sequences that can be obtained by inserting some number of ( and ) into S.

-----Sample Input-----
3
())

-----Sample Output-----
(())
user: There is a grid with N rows and N columns of squares. Let (i, j) be the square at the i-th row from the top and the j-th column from the left.
Each of the central (N-2) \times (N-2) squares in the grid has a black stone on it.
Each of the 2N - 1 squares on the bottom side and the right side has a white stone on it.
Q queries are given. We ask you to process them in order.
There are two kinds of queries. Their input format and description are as follows:
 - 1 x: Place a white stone on (1, x). After that, for each black stone between (1, x) and the first white stone you hit if you go down from (1, x), replace it with a white stone.
 - 2 x: Place a white stone on (x, 1). After that, for each black stone between (x, 1) and the first white stone you hit if you go right from (x, 1), replace it with a white stone.
How many black stones are there on the grid after processing all Q queries?

-----Constraints-----
 - 3 \leq N \leq 2\times 10^5
 - 0 \leq Q \leq \min(2N-4,2\times 10^5)
 - 2 \leq x \leq N-1
 - Queries are pairwise distinct.

-----Input-----
Input is given from Standard Input in the following format:
N Q
Query_1
\vdots
Query_Q

-----Output-----
Print how many black stones there are on the grid after processing all Q queries.

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

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

After each query, the grid changes in the following way:
user: Given are a sequence of N positive integers A_1, A_2, \ldots, A_N, and a positive integer K.
Find the number of non-empty contiguous subsequences in A such that the remainder when dividing the sum of its elements by K is equal to the number of its elements. We consider two subsequences different if they are taken from different positions, even if they are equal sequences.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2\times 10^5
 - 1 \leq K \leq 10^9
 - 1 \leq A_i \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 A_2 \cdots A_N

-----Output-----
Print the number of subsequences that satisfy the condition.

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

-----Sample Output-----
4

Four sequences satisfy the condition: (1), (4,2), (1,4,2), and (5).