meetforever/GRPO_CL huggingface dataset:
user: This is the hard version of the problem. The difference is the constraint on the sum of lengths of strings and the number of test cases. You can make hacks only if you solve all versions of this task.

You are given a string $s$, consisting of lowercase English letters. Find the longest string, $t$, which satisfies the following conditions:   The length of $t$ does not exceed the length of $s$.  $t$ is a palindrome.  There exists two strings $a$ and $b$ (possibly empty), such that $t = a + b$ ( "$+$" represents concatenation), and $a$ is prefix of $s$ while $b$ is suffix of $s$. 


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^5$), the number of test cases. The next $t$ lines each describe a test case.

Each test case is a non-empty string $s$, consisting of lowercase English letters.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed $10^6$.


-----Output-----

For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.


-----Example-----
Input
5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

Output
a
abcdfdcba
xyzyx
c
abba



-----Note-----

In the first test, the string $s = $"a" satisfies all conditions.

In the second test, the string "abcdfdcba" satisfies all conditions, because:  Its length is $9$, which does not exceed the length of the string $s$, which equals $11$.  It is a palindrome.  "abcdfdcba" $=$ "abcdfdc" $+$ "ba", and "abcdfdc" is a prefix of $s$ while "ba" is a suffix of $s$. 

It can be proven that there does not exist a longer string which satisfies the conditions.

In the fourth test, the string "c" is correct, because "c" $=$ "c" $+$ "" and $a$ or $b$ can be empty. The other possible solution for this test is "s".
user: One day Polycarp decided to rewatch his absolute favourite episode of well-known TV series "Tufurama". He was pretty surprised when he got results only for season 7 episode 3 with his search query of "Watch Tufurama season 3 episode 7 online full hd free". This got Polycarp confused — what if he decides to rewatch the entire series someday and won't be able to find the right episodes to watch? Polycarp now wants to count the number of times he will be forced to search for an episode using some different method.

TV series have n seasons (numbered 1 through n), the i-th season has a_{i} episodes (numbered 1 through a_{i}). Polycarp thinks that if for some pair of integers x and y (x < y) exist both season x episode y and season y episode x then one of these search queries will include the wrong results. Help Polycarp to calculate the number of such pairs!


-----Input-----

The first line contains one integer n (1  ≤ n  ≤  2·10^5) — the number of seasons.

The second line contains n integers separated by space a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — number of episodes in each season.


-----Output-----

Print one integer — the number of pairs x and y (x < y) such that there exist both season x episode y and season y episode x.


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

Output
0

Input
3
8 12 7

Output
3

Input
3
3 2 1

Output
2



-----Note-----

Possible pairs in the second example:  x = 1, y = 2 (season 1 episode 2 [Image] season 2 episode 1);  x = 2, y = 3 (season 2 episode 3 [Image] season 3 episode 2);  x = 1, y = 3 (season 1 episode 3 [Image] season 3 episode 1). 

In the third example:  x = 1, y = 2 (season 1 episode 2 [Image] season 2 episode 1);  x = 1, y = 3 (season 1 episode 3 [Image] season 3 episode 1).
user: Your program fails again. This time it gets "Wrong answer on test 233".

This is the harder version of the problem. In this version, $1 \le n \le 2\cdot10^5$. You can hack this problem if you locked it. But you can hack the previous problem only if you locked both problems.

The problem is to finish $n$ one-choice-questions. Each of the questions contains $k$ options, and only one of them is correct. The answer to the $i$-th question is $h_{i}$, and if your answer of the question $i$ is $h_{i}$, you earn $1$ point, otherwise, you earn $0$ points for this question. The values $h_1, h_2, \dots, h_n$ are known to you in this problem.

However, you have a mistake in your program. It moves the answer clockwise! Consider all the $n$ answers are written in a circle. Due to the mistake in your program, they are shifted by one cyclically.

Formally, the mistake moves the answer for the question $i$ to the question $i \bmod n + 1$. So it moves the answer for the question $1$ to question $2$, the answer for the question $2$ to the question $3$, ..., the answer for the question $n$ to the question $1$.

We call all the $n$ answers together an answer suit. There are $k^n$ possible answer suits in total.

You're wondering, how many answer suits satisfy the following condition: after moving clockwise by $1$, the total number of points of the new answer suit is strictly larger than the number of points of the old one. You need to find the answer modulo $998\,244\,353$.

For example, if $n = 5$, and your answer suit is $a=[1,2,3,4,5]$, it will submitted as $a'=[5,1,2,3,4]$ because of a mistake. If the correct answer suit is $h=[5,2,2,3,4]$, the answer suit $a$ earns $1$ point and the answer suite $a'$ earns $4$ points. Since $4 > 1$, the answer suit $a=[1,2,3,4,5]$ should be counted.


-----Input-----

The first line contains two integers $n$, $k$ ($1 \le n \le 2\cdot10^5$, $1 \le k \le 10^9$) — the number of questions and the number of possible answers to each question.

The following line contains $n$ integers $h_1, h_2, \dots, h_n$, ($1 \le h_{i} \le k)$ — answers to the questions.


-----Output-----

Output one integer: the number of answers suits satisfying the given condition, modulo $998\,244\,353$.


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

Output
9

Input
5 5
1 1 4 2 2

Output
1000

Input
6 2
1 1 2 2 1 1

Output
16



-----Note-----

For the first example, valid answer suits are $[2,1,1], [2,1,2], [2,1,3], [3,1,1], [3,1,2], [3,1,3], [3,2,1], [3,2,2], [3,2,3]$.
user: Little Susie, thanks to her older brother, likes to play with cars. Today she decided to set up a tournament between them. The process of a tournament is described in the next paragraph.

There are n toy cars. Each pair collides. The result of a collision can be one of the following: no car turned over, one car turned over, both cars turned over. A car is good if it turned over in no collision. The results of the collisions are determined by an n × n matrix А: there is a number on the intersection of the і-th row and j-th column that describes the result of the collision of the і-th and the j-th car:    - 1: if this pair of cars never collided.  - 1 occurs only on the main diagonal of the matrix.  0: if no car turned over during the collision.  1: if only the i-th car turned over during the collision.  2: if only the j-th car turned over during the collision.  3: if both cars turned over during the collision. 

Susie wants to find all the good cars. She quickly determined which cars are good. Can you cope with the task?


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100) — the number of cars.

Each of the next n lines contains n space-separated integers that determine matrix A. 

It is guaranteed that on the main diagonal there are  - 1, and  - 1 doesn't appear anywhere else in the matrix.

It is guaranteed that the input is correct, that is, if A_{ij} = 1, then A_{ji} = 2, if A_{ij} = 3, then A_{ji} = 3, and if A_{ij} = 0, then A_{ji} = 0.


-----Output-----

Print the number of good cars and in the next line print their space-separated indices in the increasing order.


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

Output
2
1 3 
Input
4
-1 3 3 3
3 -1 3 3
3 3 -1 3
3 3 3 -1

Output
0
user: Valera has 2·n cubes, each cube contains an integer from 10 to 99. He arbitrarily chooses n cubes and puts them in the first heap. The remaining cubes form the second heap. 

Valera decided to play with cubes. During the game he takes a cube from the first heap and writes down the number it has. Then he takes a cube from the second heap and write out its two digits near two digits he had written (to the right of them). In the end he obtained a single fourdigit integer — the first two digits of it is written on the cube from the first heap, and the second two digits of it is written on the second cube from the second heap.

Valera knows arithmetic very well. So, he can easily count the number of distinct fourdigit numbers he can get in the game. The other question is: how to split cubes into two heaps so that this number (the number of distinct fourdigit integers Valera can get) will be as large as possible?


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100). The second line contains 2·n space-separated integers a_{i} (10 ≤ a_{i} ≤ 99), denoting the numbers on the cubes.


-----Output-----

In the first line print a single number — the maximum possible number of distinct four-digit numbers Valera can obtain. In the second line print 2·n numbers b_{i} (1 ≤ b_{i} ≤ 2). The numbers mean: the i-th cube belongs to the b_{i}-th heap in your division.

If there are multiple optimal ways to split the cubes into the heaps, print any of them.


-----Examples-----
Input
1
10 99

Output
1
2 1 

Input
2
13 24 13 45

Output
4
1 2 2 1 



-----Note-----

In the first test case Valera can put the first cube in the first heap, and second cube — in second heap. In this case he obtain number 1099. If he put the second cube in the first heap, and the first cube in the second heap, then he can obtain number 9910. In both cases the maximum number of distinct integers is equal to one.

In the second test case Valera can obtain numbers 1313, 1345, 2413, 2445. Note, that if he put the first and the third cubes in the first heap, he can obtain only two numbers 1324 and 1345.
user: Guy-Manuel and Thomas have an array $a$ of $n$ integers [$a_1, a_2, \dots, a_n$]. In one step they can add $1$ to any element of the array. Formally, in one step they can choose any integer index $i$ ($1 \le i \le n$) and do $a_i := a_i + 1$.

If either the sum or the product of all elements in the array is equal to zero, Guy-Manuel and Thomas do not mind to do this operation one more time.

What is the minimum number of steps they need to do to make both the sum and the product of all elements in the array different from zero? Formally, find the minimum number of steps to make $a_1 + a_2 +$ $\dots$ $+ a_n \ne 0$ and $a_1 \cdot a_2 \cdot$ $\dots$ $\cdot a_n \ne 0$.


-----Input-----

Each test contains multiple test cases. 

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

The first line of each test case contains an integer $n$ ($1 \le n \le 100$) — the size of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($-100 \le a_i \le 100$) — elements of the array .


-----Output-----

For each test case, output the minimum number of steps required to make both sum and product of all elements in the array different from zero.


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

Output
1
2
0
2



-----Note-----

In the first test case, the sum is $0$. If we add $1$ to the first element, the array will be $[3,-1,-1]$, the sum will be equal to $1$ and the product will be equal to $3$.

In the second test case, both product and sum are $0$. If we add $1$ to the second and the third element, the array will be $[-1,1,1,1]$, the sum will be equal to $2$ and the product will be equal to $-1$. It can be shown that fewer steps can't be enough.

In the third test case, both sum and product are non-zero, we don't need to do anything.

In the fourth test case, after adding $1$ twice to the first element the array will be $[2,-2,1]$, the sum will be $1$ and the product will be $-4$.
user: Monocarp has drawn a tree (an undirected connected acyclic graph) and then has given each vertex an index. All indices are distinct numbers from $1$ to $n$. For every edge $e$ of this tree, Monocarp has written two numbers: the maximum indices of the vertices of the two components formed if the edge $e$ (and only this edge) is erased from the tree.

Monocarp has given you a list of $n - 1$ pairs of numbers. He wants you to provide an example of a tree that will produce the said list if this tree exists. If such tree does not exist, say so.


-----Input-----

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

Each of the next $n-1$ lines contains two integers $a_i$ and $b_i$ each ($1 \le a_i < b_i \le n$) — the maximal indices of vertices in the components formed if the $i$-th edge is removed.


-----Output-----

If there is no such tree that can produce the given list of pairs, print "NO" (without quotes).

Otherwise print "YES" (without quotes) in the first line and the edges of the tree in the next $n - 1$ lines. Each of the last $n - 1$ lines should contain two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$) — vertices connected by an edge.

Note: The numeration of edges doesn't matter for this task. Your solution will be considered correct if your tree produces the same pairs as given in the input file (possibly reordered). That means that you can print the edges of the tree you reconstructed in any order.


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

Output
YES
1 3
3 2
2 4

Input
3
1 3
1 3

Output
NO

Input
3
1 2
2 3

Output
NO



-----Note-----

Possible tree from the first example. Dotted lines show edges you need to remove to get appropriate pairs.  [Image]
user: One foggy Stockholm morning, Karlsson decided to snack on some jam in his friend Lillebror Svantenson's house. Fortunately for Karlsson, there wasn't anybody in his friend's house. Karlsson was not going to be hungry any longer, so he decided to get some food in the house.

Karlsson's gaze immediately fell on n wooden cupboards, standing in the kitchen. He immediately realized that these cupboards have hidden jam stocks. Karlsson began to fly greedily around the kitchen, opening and closing the cupboards' doors, grab and empty all the jars of jam that he could find.

And now all jars of jam are empty, Karlsson has had enough and does not want to leave traces of his stay, so as not to let down his friend. Each of the cupboards has two doors: the left one and the right one. Karlsson remembers that when he rushed to the kitchen, all the cupboards' left doors were in the same position (open or closed), similarly, all the cupboards' right doors were in the same position (open or closed). Karlsson wants the doors to meet this condition as well by the time the family returns. Karlsson does not remember the position of all the left doors, also, he cannot remember the position of all the right doors. Therefore, it does not matter to him in what position will be all left or right doors. It is important to leave all the left doors in the same position, and all the right doors in the same position. For example, all the left doors may be closed, and all the right ones may be open.

Karlsson needs one second to open or close a door of a cupboard. He understands that he has very little time before the family returns, so he wants to know the minimum number of seconds t, in which he is able to bring all the cupboard doors in the required position.

Your task is to write a program that will determine the required number of seconds t.


-----Input-----

The first input line contains a single integer n — the number of cupboards in the kitchen (2 ≤ n ≤ 10^4). Then follow n lines, each containing two integers l_{i} and r_{i} (0 ≤ l_{i}, r_{i} ≤ 1). Number l_{i} equals one, if the left door of the i-th cupboard is opened, otherwise number l_{i} equals zero. Similarly, number r_{i} equals one, if the right door of the i-th cupboard is opened, otherwise number r_{i} equals zero.

The numbers in the lines are separated by single spaces.


-----Output-----

In the only output line print a single integer t — the minimum number of seconds Karlsson needs to change the doors of all cupboards to the position he needs.


-----Examples-----
Input
5
0 1
1 0
0 1
1 1
0 1

Output
3
user: You are given three multisets of pairs of colored sticks:   $R$ pairs of red sticks, the first pair has length $r_1$, the second pair has length $r_2$, $\dots$, the $R$-th pair has length $r_R$;  $G$ pairs of green sticks, the first pair has length $g_1$, the second pair has length $g_2$, $\dots$, the $G$-th pair has length $g_G$;  $B$ pairs of blue sticks, the first pair has length $b_1$, the second pair has length $b_2$, $\dots$, the $B$-th pair has length $b_B$; 

You are constructing rectangles from these pairs of sticks with the following process:   take a pair of sticks of one color;  take a pair of sticks of another color different from the first one;  add the area of the resulting rectangle to the total area. 

Thus, you get such rectangles that their opposite sides are the same color and their adjacent sides are not the same color.

Each pair of sticks can be used at most once, some pairs can be left unused. You are not allowed to split a pair into independent sticks.

What is the maximum area you can achieve?


-----Input-----

The first line contains three integers $R$, $G$, $B$ ($1 \le R, G, B \le 200$) — the number of pairs of red sticks, the number of pairs of green sticks and the number of pairs of blue sticks.

The second line contains $R$ integers $r_1, r_2, \dots, r_R$ ($1 \le r_i \le 2000$) — the lengths of sticks in each pair of red sticks.

The third line contains $G$ integers $g_1, g_2, \dots, g_G$ ($1 \le g_i \le 2000$) — the lengths of sticks in each pair of green sticks.

The fourth line contains $B$ integers $b_1, b_2, \dots, b_B$ ($1 \le b_i \le 2000$) — the lengths of sticks in each pair of blue sticks.


-----Output-----

Print the maximum possible total area of the constructed rectangles.


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

Output
20

Input
2 1 3
9 5
1
2 8 5

Output
99

Input
10 1 1
11 7 20 15 19 14 2 4 13 14
8
11

Output
372



-----Note-----

In the first example you can construct one of these rectangles: red and green with sides $3$ and $5$, red and blue with sides $3$ and $4$ and green and blue with sides $5$ and $4$. The best area of them is $4 \times 5 = 20$.

In the second example the best rectangles are: red/blue $9 \times 8$, red/blue $5 \times 5$, green/blue $2 \times 1$. So the total area is $72 + 25 + 2 = 99$.

In the third example the best rectangles are: red/green $19 \times 8$ and red/blue $20 \times 11$. The total area is $152 + 220 = 372$. Note that you can't construct more rectangles because you are not allowed to have both pairs taken to be the same color.
user: After battling Shikamaru, Tayuya decided that her flute is too predictable, and replaced it with a guitar. The guitar has $6$ strings and an infinite number of frets numbered from $1$. Fretting the fret number $j$ on the $i$-th string produces the note $a_{i} + j$.

Tayuya wants to play a melody of $n$ notes. Each note can be played on different string-fret combination. The easiness of performance depends on the difference between the maximal and the minimal indices of used frets. The less this difference is, the easier it is to perform the technique. Please determine the minimal possible difference.

For example, if $a = [1, 1, 2, 2, 3, 3]$, and the sequence of notes is $4, 11, 11, 12, 12, 13, 13$ (corresponding to the second example), we can play the first note on the first string, and all the other notes on the sixth string. Then the maximal fret will be $10$, the minimal one will be $3$, and the answer is $10 - 3 = 7$, as shown on the picture. [Image] 


-----Input-----

The first line contains $6$ space-separated numbers $a_{1}$, $a_{2}$, ..., $a_{6}$ ($1 \leq a_{i} \leq 10^{9}$) which describe the Tayuya's strings.

The second line contains the only integer $n$ ($1 \leq n \leq 100\,000$) standing for the number of notes in the melody.

The third line consists of $n$ integers $b_{1}$, $b_{2}$, ..., $b_{n}$ ($1 \leq b_{i} \leq 10^{9}$), separated by space. They describe the notes to be played. It's guaranteed that $b_i > a_j$ for all $1\leq i\leq n$ and $1\leq j\leq 6$, in other words, you can play each note on any string.


-----Output-----

Print the minimal possible difference of the maximal and the minimal indices of used frets.


-----Examples-----
Input
1 4 100 10 30 5
6
101 104 105 110 130 200

Output
0

Input
1 1 2 2 3 3
7
13 4 11 12 11 13 12

Output
7



-----Note-----

In the first sample test it is optimal to play the first note on the first string, the second note on the second string, the third note on the sixth string, the fourth note on the fourth string, the fifth note on the fifth string, and the sixth note on the third string. In this case the $100$-th fret is used each time, so the difference is $100 - 100 = 0$. [Image] 

In the second test it's optimal, for example, to play the second note on the first string, and all the other notes on the sixth string. Then the maximal fret will be $10$, the minimal one will be $3$, and the answer is $10 - 3 = 7$. [Image]
user: Given an array $a$ of length $n$, find another array, $b$, of length $n$ such that:

  for each $i$ $(1 \le i \le n)$ $MEX(\{b_1$, $b_2$, $\ldots$, $b_i\})=a_i$. 

The $MEX$ of a set of integers is the smallest non-negative integer that doesn't belong to this set.

If such array doesn't exist, determine this.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($0 \le a_i \le i$) — the elements of the array $a$. It's guaranteed that $a_i \le a_{i+1}$ for $1\le i < n$. 


-----Output-----

If there's no such array, print a single line containing $-1$.

Otherwise, print a single line containing $n$ integers $b_1$, $b_2$, $\ldots$, $b_n$ ($0 \le b_i \le 10^6$)

If there are multiple answers, print any.


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

Output
0 1 2 
Input
4
0 0 0 2

Output
1 3 4 0 
Input
3
1 1 3

Output
0 2 1 


-----Note-----

In the second test case, other answers like $[1,1,1,0]$, for example, are valid.
user: You are given a set of all integers from $l$ to $r$ inclusive, $l < r$, $(r - l + 1) \le 3 \cdot 10^5$ and $(r - l)$ is always odd.

You want to split these numbers into exactly $\frac{r - l + 1}{2}$ pairs in such a way that for each pair $(i, j)$ the greatest common divisor of $i$ and $j$ is equal to $1$. Each number should appear in exactly one of the pairs.

Print the resulting pairs or output that no solution exists. If there are multiple solutions, print any of them.


-----Input-----

The only line contains two integers $l$ and $r$ ($1 \le l < r \le 10^{18}$, $r - l + 1 \le 3 \cdot 10^5$, $(r - l)$ is odd).


-----Output-----

If any solution exists, print "YES" in the first line. Each of the next $\frac{r - l + 1}{2}$ lines should contain some pair of integers. GCD of numbers in each pair should be equal to $1$. All $(r - l + 1)$ numbers should be pairwise distinct and should have values from $l$ to $r$ inclusive.

If there are multiple solutions, print any of them.

If there exists no solution, print "NO".


-----Example-----
Input
1 8

Output
YES
2 7
4 1
3 8
6 5