meetforever/GRPO_CL huggingface dataset:
user: In Summer Informatics School, if a student doesn't behave well, teachers make a hole in his badge. And today one of the teachers caught a group of $n$ students doing yet another trick. 

Let's assume that all these students are numbered from $1$ to $n$. The teacher came to student $a$ and put a hole in his badge. The student, however, claimed that the main culprit is some other student $p_a$.

After that, the teacher came to student $p_a$ and made a hole in his badge as well. The student in reply said that the main culprit was student $p_{p_a}$.

This process went on for a while, but, since the number of students was finite, eventually the teacher came to the student, who already had a hole in his badge.

After that, the teacher put a second hole in the student's badge and decided that he is done with this process, and went to the sauna.

You don't know the first student who was caught by the teacher. However, you know all the numbers $p_i$. Your task is to find out for every student $a$, who would be the student with two holes in the badge if the first caught student was $a$.


-----Input-----

The first line of the input contains the only integer $n$ ($1 \le n \le 1000$) — the number of the naughty students.

The second line contains $n$ integers $p_1$, ..., $p_n$ ($1 \le p_i \le n$), where $p_i$ indicates the student who was reported to the teacher by student $i$.


-----Output-----

For every student $a$ from $1$ to $n$ print which student would receive two holes in the badge, if $a$ was the first student caught by the teacher.


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

Output
2 2 3 

Input
3
1 2 3

Output
1 2 3 



-----Note-----

The picture corresponds to the first example test case.

 $8$ 

When $a = 1$, the teacher comes to students $1$, $2$, $3$, $2$, in this order, and the student $2$ is the one who receives a second hole in his badge.

When $a = 2$, the teacher comes to students $2$, $3$, $2$, and the student $2$ gets a second hole in his badge. When $a = 3$, the teacher will visit students $3$, $2$, $3$ with student $3$ getting a second hole in his badge.

For the second example test case it's clear that no matter with whom the teacher starts, that student would be the one who gets the second hole in his badge.
user: Let's denote that some array $b$ is bad if it contains a subarray $b_l, b_{l+1}, \dots, b_{r}$ of odd length more than $1$ ($l < r$ and $r - l + 1$ is odd) such that $\forall i \in \{0, 1, \dots, r - l\}$ $b_{l + i} = b_{r - i}$.

If an array is not bad, it is good.

Now you are given an array $a_1, a_2, \dots, a_n$. Some elements are replaced by $-1$. Calculate the number of good arrays you can obtain by replacing each $-1$ with some integer from $1$ to $k$.

Since the answer can be large, print it modulo $998244353$.


-----Input-----

The first line contains two integers $n$ and $k$ ($2 \le n, k \le 2 \cdot 10^5$) — the length of array $a$ and the size of "alphabet", i. e., the upper bound on the numbers you may use to replace $-1$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($a_i = -1$ or $1 \le a_i \le k$) — the array $a$.


-----Output-----

Print one integer — the number of good arrays you can get, modulo $998244353$.


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

Output
9

Input
5 2
1 -1 -1 1 2

Output
0

Input
5 3
1 -1 -1 1 2

Output
2

Input
4 200000
-1 -1 12345 -1

Output
735945883
user: There are three horses living in a horse land: one gray, one white and one gray-and-white. The horses are really amusing animals, which is why they adore special cards. Each of those cards must contain two integers, the first one on top, the second one in the bottom of the card. Let's denote a card with a on the top and b in the bottom as (a, b).

Each of the three horses can paint the special cards. If you show an (a, b) card to the gray horse, then the horse can paint a new (a + 1, b + 1) card. If you show an (a, b) card, such that a and b are even integers, to the white horse, then the horse can paint a new $(\frac{a}{2}, \frac{b}{2})$ card. If you show two cards (a, b) and (b, c) to the gray-and-white horse, then he can paint a new (a, c) card.

Polycarpus really wants to get n special cards (1, a_1), (1, a_2), ..., (1, a_{n}). For that he is going to the horse land. He can take exactly one (x, y) card to the horse land, such that 1 ≤ x < y ≤ m. How many ways are there to choose the card so that he can perform some actions in the horse land and get the required cards?

Polycarpus can get cards from the horses only as a result of the actions that are described above. Polycarpus is allowed to get additional cards besides the cards that he requires.


-----Input-----

The first line contains two integers n, m (1 ≤ n ≤ 10^5, 2 ≤ m ≤ 10^9). The second line contains the sequence of integers a_1, a_2, ..., a_{n} (2 ≤ a_{i} ≤ 10^9). Note, that the numbers in the sequence can coincide.

The numbers in the lines are separated by single spaces.


-----Output-----

Print a single integer — the answer to the problem. 

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.


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

Output
11

Input
1 6
7

Output
14

Input
2 10
13 7

Output
36
user: All cities of Lineland are located on the Ox coordinate axis. Thus, each city is associated with its position x_{i} — a coordinate on the Ox axis. No two cities are located at a single point.

Lineland residents love to send letters to each other. A person may send a letter only if the recipient lives in another city (because if they live in the same city, then it is easier to drop in).

Strange but true, the cost of sending the letter is exactly equal to the distance between the sender's city and the recipient's city.

For each city calculate two values ​​min_{i} and max_{i}, where min_{i} is the minimum cost of sending a letter from the i-th city to some other city, and max_{i} is the the maximum cost of sending a letter from the i-th city to some other city


-----Input-----

The first line of the input contains integer n (2 ≤ n ≤ 10^5) — the number of cities in Lineland. The second line contains the sequence of n distinct integers x_1, x_2, ..., x_{n} ( - 10^9 ≤ x_{i} ≤ 10^9), where x_{i} is the x-coordinate of the i-th city. All the x_{i}'s are distinct and follow in ascending order.


-----Output-----

Print n lines, the i-th line must contain two integers min_{i}, max_{i}, separated by a space, where min_{i} is the minimum cost of sending a letter from the i-th city, and max_{i} is the maximum cost of sending a letter from the i-th city.


-----Examples-----
Input
4
-5 -2 2 7

Output
3 12
3 9
4 7
5 12

Input
2
-1 1

Output
2 2
2 2
user: Little Susie loves strings. Today she calculates distances between them. As Susie is a small girl after all, her strings contain only digits zero and one. She uses the definition of Hamming distance:

We will define the distance between two strings s and t of the same length consisting of digits zero and one as the number of positions i, such that s_{i} isn't equal to t_{i}. 

As besides everything else Susie loves symmetry, she wants to find for two strings s and t of length n such string p of length n, that the distance from p to s was equal to the distance from p to t.

It's time for Susie to go to bed, help her find such string p or state that it is impossible.


-----Input-----

The first line contains string s of length n. 

The second line contains string t of length n.

The length of string n is within range from 1 to 10^5. It is guaranteed that both strings contain only digits zero and one.


-----Output-----

Print a string of length n, consisting of digits zero and one, that meets the problem statement. If no such string exist, print on a single line "impossible" (without the quotes).

If there are multiple possible answers, print any of them.


-----Examples-----
Input
0001
1011

Output
0011

Input
000
111

Output
impossible



-----Note-----

In the first sample different answers are possible, namely — 0010, 0011, 0110, 0111, 1000, 1001, 1100, 1101.
user: Iahub is a big fan of tourists. He wants to become a tourist himself, so he planned a trip. There are n destinations on a straight road that Iahub wants to visit. Iahub starts the excursion from kilometer 0. The n destinations are described by a non-negative integers sequence a_1, a_2, ..., a_{n}. The number a_{k} represents that the kth destination is at distance a_{k} kilometers from the starting point. No two destinations are located in the same place. 

Iahub wants to visit each destination only once. Note that, crossing through a destination is not considered visiting, unless Iahub explicitly wants to visit it at that point. Also, after Iahub visits his last destination, he doesn't come back to kilometer 0, as he stops his trip at the last destination. 

The distance between destination located at kilometer x and next destination, located at kilometer y, is |x - y| kilometers. We call a "route" an order of visiting the destinations. Iahub can visit destinations in any order he wants, as long as he visits all n destinations and he doesn't visit a destination more than once. 

Iahub starts writing out on a paper all possible routes and for each of them, he notes the total distance he would walk. He's interested in the average number of kilometers he would walk by choosing a route. As he got bored of writing out all the routes, he asks you to help him.


-----Input-----

The first line contains integer n (2 ≤ n ≤ 10^5). Next line contains n distinct integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^7).


-----Output-----

Output two integers — the numerator and denominator of a fraction which is equal to the wanted average number. The fraction must be irreducible.


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

Output
22 3


-----Note-----

Consider 6 possible routes:  [2, 3, 5]: total distance traveled: |2 – 0| + |3 – 2| + |5 – 3| = 5;  [2, 5, 3]: |2 – 0| + |5 – 2| + |3 – 5| = 7;  [3, 2, 5]: |3 – 0| + |2 – 3| + |5 – 2| = 7;  [3, 5, 2]: |3 – 0| + |5 – 3| + |2 – 5| = 8;  [5, 2, 3]: |5 – 0| + |2 – 5| + |3 – 2| = 9;  [5, 3, 2]: |5 – 0| + |3 – 5| + |2 – 3| = 8. 

The average travel distance is $\frac{1}{6} \cdot(5 + 7 + 7 + 8 + 9 + 8)$ = $\frac{44}{6}$ = $\frac{22}{3}$.
user: You are given n distinct points on a plane with integral coordinates. For each point you can either draw a vertical line through it, draw a horizontal line through it, or do nothing.

You consider several coinciding straight lines as a single one. How many distinct pictures you can get? Print the answer modulo 10^9 + 7.


-----Input-----

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

n lines follow. The (i + 1)-th of these lines contains two integers x_{i}, y_{i} ( - 10^9 ≤ x_{i}, y_{i} ≤ 10^9) — coordinates of the i-th point.

It is guaranteed that all points are distinct.


-----Output-----

Print the number of possible distinct pictures modulo 10^9 + 7.


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

Output
16

Input
2
-1 -1
0 1

Output
9



-----Note-----

In the first example there are two vertical and two horizontal lines passing through the points. You can get pictures with any subset of these lines. For example, you can get the picture containing all four lines in two ways (each segment represents a line containing it). The first way:   [Image]   The second way:   [Image] 

In the second example you can work with two points independently. The number of pictures is 3^2 = 9.
user: In Berland recently a new collection of toys went on sale. This collection consists of 10^9 types of toys, numbered with integers from 1 to 10^9. A toy from the new collection of the i-th type costs i bourles.

Tania has managed to collect n different types of toys a_1, a_2, ..., a_{n} from the new collection. Today is Tanya's birthday, and her mother decided to spend no more than m bourles on the gift to the daughter. Tanya will choose several different types of toys from the new collection as a gift. Of course, she does not want to get a type of toy which she already has.

Tanya wants to have as many distinct types of toys in her collection as possible as the result. The new collection is too diverse, and Tanya is too little, so she asks you to help her in this.


-----Input-----

The first line contains two integers n (1 ≤ n ≤ 100 000) and m (1 ≤ m ≤ 10^9) — the number of types of toys that Tanya already has and the number of bourles that her mom is willing to spend on buying new toys.

The next line contains n distinct integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the types of toys that Tanya already has.


-----Output-----

In the first line print a single integer k — the number of different types of toys that Tanya should choose so that the number of different types of toys in her collection is maximum possible. Of course, the total cost of the selected toys should not exceed m.

In the second line print k distinct space-separated integers t_1, t_2, ..., t_{k} (1 ≤ t_{i} ≤ 10^9) — the types of toys that Tanya should choose.

If there are multiple answers, you may print any of them. Values of t_{i} can be printed in any order.


-----Examples-----
Input
3 7
1 3 4

Output
2
2 5 

Input
4 14
4 6 12 8

Output
4
7 2 3 1



-----Note-----

In the first sample mom should buy two toys: one toy of the 2-nd type and one toy of the 5-th type. At any other purchase for 7 bourles (assuming that the toys of types 1, 3 and 4 have already been bought), it is impossible to buy two and more toys.
user: Ann and Borya have n piles with candies and n is even number. There are a_{i} candies in pile with number i.

Ann likes numbers which are square of some integer and Borya doesn't like numbers which are square of any integer. During one move guys can select some pile with candies and add one candy to it (this candy is new and doesn't belong to any other pile) or remove one candy (if there is at least one candy in this pile). 

Find out minimal number of moves that is required to make exactly n / 2 piles contain number of candies that is a square of some integer and exactly n / 2 piles contain number of candies that is not a square of any integer.


-----Input-----

First line contains one even integer n (2 ≤ n ≤ 200 000) — number of piles with candies.

Second line contains sequence of integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9) — amounts of candies in each pile.


-----Output-----

Output minimal number of steps required to make exactly n / 2 piles contain number of candies that is a square of some integer and exactly n / 2 piles contain number of candies that is not a square of any integer. If condition is already satisfied output 0.


-----Examples-----
Input
4
12 14 30 4

Output
2

Input
6
0 0 0 0 0 0

Output
6

Input
6
120 110 23 34 25 45

Output
3

Input
10
121 56 78 81 45 100 1 0 54 78

Output
0



-----Note-----

In first example you can satisfy condition in two moves. During each move you should add one candy to second pile. After it size of second pile becomes 16. After that Borya and Ann will have two piles with number of candies which is a square of integer (second and fourth pile) and two piles with number of candies which is not a square of any integer (first and third pile).

In second example you should add two candies to any three piles.
user: The Berland Forest can be represented as an infinite cell plane. Every cell contains a tree. That is, contained before the recent events.

A destructive fire raged through the Forest, and several trees were damaged by it. Precisely speaking, you have a $n \times m$ rectangle map which represents the damaged part of the Forest. The damaged trees were marked as "X" while the remaining ones were marked as ".". You are sure that all burnt trees are shown on the map. All the trees outside the map are undamaged.

The firemen quickly extinguished the fire, and now they are investigating the cause of it. The main version is that there was an arson: at some moment of time (let's consider it as $0$) some trees were set on fire. At the beginning of minute $0$, only the trees that were set on fire initially were burning. At the end of each minute, the fire spread from every burning tree to each of $8$ neighboring trees. At the beginning of minute $T$, the fire was extinguished.

The firemen want to find the arsonists as quickly as possible. The problem is, they know neither the value of $T$ (how long the fire has been raging) nor the coordinates of the trees that were initially set on fire. They want you to find the maximum value of $T$ (to know how far could the arsonists escape) and a possible set of trees that could be initially set on fire.

Note that you'd like to maximize value $T$ but the set of trees can be arbitrary.


-----Input-----

The first line contains two integer $n$ and $m$ ($1 \le n, m \le 10^6$, $1 \le n \cdot m \le 10^6$) — the sizes of the map.

Next $n$ lines contain the map. The $i$-th line corresponds to the $i$-th row of the map and contains $m$-character string. The $j$-th character of the $i$-th string is "X" if the corresponding tree is burnt and "." otherwise.

It's guaranteed that the map contains at least one "X".


-----Output-----

In the first line print the single integer $T$ — the maximum time the Forest was on fire. In the next $n$ lines print the certificate: the map ($n \times m$ rectangle) where the trees that were set on fire are marked as "X" and all other trees are marked as ".".


-----Examples-----
Input
3 6
XXXXXX
XXXXXX
XXXXXX

Output
1
......
.X.XX.
......

Input
10 10
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
..........

Output
2
..........
..........
...XX.....
..........
..........
..........
.....XX...
..........
..........
..........

Input
4 5
X....
..XXX
..XXX
..XXX

Output
0
X....
..XXX
..XXX
..XXX
user: DZY loves chessboard, and he enjoys playing with it.

He has a chessboard of n rows and m columns. Some cells of the chessboard are bad, others are good. For every good cell, DZY wants to put a chessman on it. Each chessman is either white or black. After putting all chessmen, DZY wants that no two chessmen with the same color are on two adjacent cells. Two cells are adjacent if and only if they share a common edge.

You task is to find any suitable placement of chessmen on the given chessboard.


-----Input-----

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 100).

Each of the next n lines contains a string of m characters: the j-th character of the i-th string is either "." or "-". A "." means that the corresponding cell (in the i-th row and the j-th column) is good, while a "-" means it is bad.


-----Output-----

Output must contain n lines, each line must contain a string of m characters. The j-th character of the i-th string should be either "W", "B" or "-". Character "W" means the chessman on the cell is white, "B" means it is black, "-" means the cell is a bad cell.

If multiple answers exist, print any of them. It is guaranteed that at least one answer exists.


-----Examples-----
Input
1 1
.

Output
B

Input
2 2
..
..

Output
BW
WB

Input
3 3
.-.
---
--.
Output
B-B
---
--B


-----Note-----

In the first sample, DZY puts a single black chessman. Of course putting a white one is also OK.

In the second sample, all 4 cells are good. No two same chessmen share an edge in the sample output.

In the third sample, no good cells are adjacent. So you can just put 3 chessmen, no matter what their colors are.
user: Dreamoon has a string s and a pattern string p. He first removes exactly x characters from s obtaining string s' as a result. Then he calculates $\operatorname{occ}(s^{\prime}, p)$ that is defined as the maximal number of non-overlapping substrings equal to p that can be found in s'. He wants to make this number as big as possible.

More formally, let's define $\operatorname{ans}(x)$ as maximum value of $\operatorname{occ}(s^{\prime}, p)$ over all s' that can be obtained by removing exactly x characters from s. Dreamoon wants to know $\operatorname{ans}(x)$ for all x from 0 to |s| where |s| denotes the length of string s.


-----Input-----

The first line of the input contains the string s (1 ≤ |s| ≤ 2 000).

The second line of the input contains the string p (1 ≤ |p| ≤ 500).

Both strings will only consist of lower case English letters.


-----Output-----

Print |s| + 1 space-separated integers in a single line representing the $\operatorname{ans}(x)$ for all x from 0 to |s|.


-----Examples-----
Input
aaaaa
aa

Output
2 2 1 1 0 0

Input
axbaxxb
ab

Output
0 1 1 2 1 1 0 0



-----Note-----

For the first sample, the corresponding optimal values of s' after removal 0 through |s| = 5 characters from s are {"aaaaa", "aaaa", "aaa", "aa", "a", ""}. 

For the second sample, possible corresponding optimal values of s' are {"axbaxxb", "abaxxb", "axbab", "abab", "aba", "ab", "a", ""}.
user: Amr loves Chemistry, and specially doing experiments. He is preparing for a new interesting experiment.

Amr has n different types of chemicals. Each chemical i has an initial volume of a_{i} liters. For this experiment, Amr has to mix all the chemicals together, but all the chemicals volumes must be equal first. So his task is to make all the chemicals volumes equal.

To do this, Amr can do two different kind of operations.   Choose some chemical i and double its current volume so the new volume will be 2a_{i}  Choose some chemical i and divide its volume by two (integer division) so the new volume will be $\lfloor \frac{a_{i}}{2} \rfloor$ 

Suppose that each chemical is contained in a vessel of infinite volume. Now Amr wonders what is the minimum number of operations required to make all the chemicals volumes equal?


-----Input-----

The first line contains one number n (1 ≤ n ≤ 10^5), the number of chemicals.

The second line contains n space separated integers a_{i} (1 ≤ a_{i} ≤ 10^5), representing the initial volume of the i-th chemical in liters.


-----Output-----

Output one integer the minimum number of operations required to make all the chemicals volumes equal.


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

Output
2
Input
3
3 5 6

Output
5


-----Note-----

In the first sample test, the optimal solution is to divide the second chemical volume by two, and multiply the third chemical volume by two to make all the volumes equal 4.

In the second sample test, the optimal solution is to divide the first chemical volume by two, and divide the second and the third chemical volumes by two twice to make all the volumes equal 1.