meetforever/GRPO_CL huggingface dataset:
user: Mrs. Smith is trying to contact her husband, John Smith, but she forgot the secret phone number!

The only thing Mrs. Smith remembered was that any permutation of $n$ can be a secret phone number. Only those permutations that minimize secret value might be the phone of her husband.

The sequence of $n$ integers is called a permutation if it contains all integers from $1$ to $n$ exactly once.

The secret value of a phone number is defined as the sum of the length of the longest increasing subsequence (LIS) and length of the longest decreasing subsequence (LDS). 

A subsequence $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ where $1\leq i_1 < i_2 < \ldots < i_k\leq n$ is called increasing if $a_{i_1} < a_{i_2} < a_{i_3} < \ldots < a_{i_k}$. If $a_{i_1} > a_{i_2} > a_{i_3} > \ldots > a_{i_k}$, a subsequence is called decreasing. An increasing/decreasing subsequence is called longest if it has maximum length among all increasing/decreasing subsequences.

For example, if there is a permutation $[6, 4, 1, 7, 2, 3, 5]$, LIS of this permutation will be $[1, 2, 3, 5]$, so the length of LIS is equal to $4$. LDS can be $[6, 4, 1]$, $[6, 4, 2]$, or $[6, 4, 3]$, so the length of LDS is $3$.

Note, the lengths of LIS and LDS can be different.

So please help Mrs. Smith to find a permutation that gives a minimum sum of lengths of LIS and LDS.


-----Input-----

The only line contains one integer $n$ ($1 \le n \le 10^5$) — the length of permutation that you need to build.


-----Output-----

Print a permutation that gives a minimum sum of lengths of LIS and LDS. 

If there are multiple answers, print any.


-----Examples-----
Input
4

Output
3 4 1 2

Input
2

Output
2 1



-----Note-----

In the first sample, you can build a permutation $[3, 4, 1, 2]$. LIS is $[3, 4]$ (or $[1, 2]$), so the length of LIS is equal to $2$. LDS can be ony of $[3, 1]$, $[4, 2]$, $[3, 2]$, or $[4, 1]$. The length of LDS is also equal to $2$. The sum is equal to $4$. Note that $[3, 4, 1, 2]$ is not the only permutation that is valid.

In the second sample, you can build a permutation $[2, 1]$. LIS is $[1]$ (or $[2]$), so the length of LIS is equal to $1$. LDS is $[2, 1]$, so the length of LDS is equal to $2$. The sum is equal to $3$. Note that permutation $[1, 2]$ is also valid.
user: You're playing a game called Osu! Here's a simplified version of it. There are n clicks in a game. For each click there are two outcomes: correct or bad. Let us denote correct as "O", bad as "X", then the whole play can be encoded as a sequence of n characters "O" and "X".

Using the play sequence you can calculate the score for the play as follows: for every maximal consecutive "O"s block, add the square of its length (the number of characters "O") to the score. For example, if your play can be encoded as "OOXOOOXXOO", then there's three maximal consecutive "O"s block "OO", "OOO", "OO", so your score will be 2^2 + 3^2 + 2^2 = 17. If there are no correct clicks in a play then the score for the play equals to 0.

You know that the probability to click the i-th (1 ≤ i ≤ n) click correctly is p_{i}. In other words, the i-th character in the play sequence has p_{i} probability to be "O", 1 - p_{i} to be "X". You task is to calculate the expected score for your play.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of clicks. The second line contains n space-separated real numbers p_1, p_2, ..., p_{n} (0 ≤ p_{i} ≤ 1).

There will be at most six digits after the decimal point in the given p_{i}.


-----Output-----

Print a single real number — the expected score for your play. Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}.


-----Examples-----
Input
3
0.5 0.5 0.5

Output
2.750000000000000

Input
4
0.7 0.2 0.1 0.9

Output
2.489200000000000

Input
5
1 1 1 1 1

Output
25.000000000000000



-----Note-----

For the first example. There are 8 possible outcomes. Each has a probability of 0.125.  "OOO"  →  3^2 = 9;  "OOX"  →  2^2 = 4;  "OXO"  →  1^2 + 1^2 = 2;  "OXX"  →  1^2 = 1;  "XOO"  →  2^2 = 4;  "XOX"  →  1^2 = 1;  "XXO"  →  1^2 = 1;  "XXX"  →  0. 

So the expected score is $\frac{9 + 4 + 2 + 1 + 4 + 1 + 1}{8} = 2.75$
user: Vasya and Petya are playing a simple game. Vasya thought of number x between 1 and n, and Petya tries to guess the number.

Petya can ask questions like: "Is the unknown number divisible by number y?".

The game is played by the following rules: first Petya asks all the questions that interest him (also, he can ask no questions), and then Vasya responds to each question with a 'yes' or a 'no'. After receiving all the answers Petya should determine the number that Vasya thought of.

Unfortunately, Petya is not familiar with the number theory. Help him find the minimum number of questions he should ask to make a guaranteed guess of Vasya's number, and the numbers y_{i}, he should ask the questions about.


-----Input-----

A single line contains number n (1 ≤ n ≤ 10^3).


-----Output-----

Print the length of the sequence of questions k (0 ≤ k ≤ n), followed by k numbers — the questions y_{i} (1 ≤ y_{i} ≤ n).

If there are several correct sequences of questions of the minimum length, you are allowed to print any of them.


-----Examples-----
Input
4

Output
3
2 4 3 

Input
6

Output
4
2 4 3 5 



-----Note-----

The sequence from the answer to the first sample test is actually correct.

If the unknown number is not divisible by one of the sequence numbers, it is equal to 1.

If the unknown number is divisible by 4, it is 4.

If the unknown number is divisible by 3, then the unknown number is 3.

Otherwise, it is equal to 2. Therefore, the sequence of questions allows you to guess the unknown number. It can be shown that there is no correct sequence of questions of length 2 or shorter.
user: Yaroslav is playing a game called "Time". The game has a timer showing the lifespan he's got left. As soon as the timer shows 0, Yaroslav's character dies and the game ends. Also, the game has n clock stations, station number i is at point (x_{i}, y_{i}) of the plane. As the player visits station number i, he increases the current time on his timer by a_{i}. The stations are for one-time use only, so if the player visits some station another time, the time on his timer won't grow.

A player spends d·dist time units to move between stations, where dist is the distance the player has covered and d is some constant. The distance between stations i and j is determined as |x_{i} - x_{j}| + |y_{i} - y_{j}|.

Initially, the player is at station number 1, and the player has strictly more than zero and strictly less than one units of time. At station number 1 one unit of money can increase the time on the timer by one time unit (you can buy only integer number of time units).

Now Yaroslav is wondering, how much money he needs to get to station n. Help Yaroslav. Consider the time to buy and to increase the timer value negligibly small.


-----Input-----

The first line contains integers n and d (3 ≤ n ≤ 100, 10^3 ≤ d ≤ 10^5) — the number of stations and the constant from the statement.

The second line contains n - 2 integers: a_2, a_3, ..., a_{n} - 1 (1 ≤ a_{i} ≤ 10^3). The next n lines contain the coordinates of the stations. The i-th of them contains two integers x_{i}, y_{i} (-100 ≤ x_{i}, y_{i} ≤ 100).

It is guaranteed that no two stations are located at the same point.


-----Output-----

In a single line print an integer — the answer to the problem.


-----Examples-----
Input
3 1000
1000
0 0
0 1
0 3

Output
2000

Input
3 1000
1000
1 0
1 1
1 2

Output
1000
user: Squirrel Liss lived in a forest peacefully, but unexpected trouble happens. Stones fall from a mountain. Initially Squirrel Liss occupies an interval [0, 1]. Next, n stones will fall and Liss will escape from the stones. The stones are numbered from 1 to n in order.

The stones always fall to the center of Liss's interval. When Liss occupies the interval [k - d, k + d] and a stone falls to k, she will escape to the left or to the right. If she escapes to the left, her new interval will be [k - d, k]. If she escapes to the right, her new interval will be [k, k + d].

You are given a string s of length n. If the i-th character of s is "l" or "r", when the i-th stone falls Liss will escape to the left or to the right, respectively. Find the sequence of stones' numbers from left to right after all the n stones falls.


-----Input-----

The input consists of only one line. The only line contains the string s (1 ≤ |s| ≤ 10^6). Each character in s will be either "l" or "r".


-----Output-----

Output n lines — on the i-th line you should print the i-th stone's number from the left.


-----Examples-----
Input
llrlr

Output
3
5
4
2
1

Input
rrlll

Output
1
2
5
4
3

Input
lrlrr

Output
2
4
5
3
1



-----Note-----

In the first example, the positions of stones 1, 2, 3, 4, 5 will be $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{3}{16}, \frac{5}{32}$, respectively. So you should print the sequence: 3, 5, 4, 2, 1.
user: Reading books is one of Sasha's passions. Once while he was reading one book, he became acquainted with an unusual character. The character told about himself like that: "Many are my names in many countries. Mithrandir among the Elves, Tharkûn to the Dwarves, Olórin I was in my youth in the West that is forgotten, in the South Incánus, in the North Gandalf; to the East I go not."

And at that moment Sasha thought, how would that character be called in the East? In the East all names are palindromes. A string is a palindrome if it reads the same backward as forward. For example, such strings as "kazak", "oo" and "r" are palindromes, but strings "abb" and "ij" are not. 

Sasha believed that the hero would be named after one of the gods of the East. As long as there couldn't be two equal names, so in the East people did the following: they wrote the original name as a string on a piece of paper, then cut the paper minimum number of times $k$, so they got $k+1$ pieces of paper with substrings of the initial string, and then unite those pieces together to get a new string. Pieces couldn't be turned over, they could be shuffled.

In this way, it's possible to achive a string abcdefg from the string f|de|abc|g using $3$ cuts (by swapping papers with substrings f and abc). The string cbadefg can't be received using the same cuts.

More formally, Sasha wants for the given palindrome $s$ find such minimum $k$, that you can cut this string into $k + 1$ parts, and then unite them in such a way that the final string will be a palindrome and it won't be equal to the initial string $s$. It there is no answer, then print "Impossible" (without quotes).


-----Input-----

The first line contains one string $s$ ($1 \le |s| \le 5\,000$) — the initial name, which consists only of lowercase Latin letters. It is guaranteed that $s$ is a palindrome.


-----Output-----

Print one integer $k$ — the minimum number of cuts needed to get a new name, or "Impossible" (without quotes).


-----Examples-----
Input
nolon

Output
2

Input
otto

Output
1

Input
qqqq

Output
Impossible

Input
kinnikkinnik

Output
1



-----Note-----

In the first example, you can cut the string in those positions: no|l|on, and then unite them as follows on|l|no. It can be shown that there is no solution with one cut.

In the second example, you can cut the string right in the middle, and swap peaces, so you get toot.

In the third example, you can't make a string, that won't be equal to the initial one.

In the fourth example, you can cut the suffix nik and add it to the beginning, so you get nikkinnikkin.
user: You are given integer $n$. You have to arrange numbers from $1$ to $2n$, using each of them exactly once, on the circle, so that the following condition would be satisfied:

For every $n$ consecutive numbers on the circle write their sum on the blackboard. Then any two of written on the blackboard $2n$ numbers differ not more than by $1$.

For example, choose $n = 3$. On the left you can see an example of a valid arrangement: $1 + 4 + 5 = 10$, $4 + 5 + 2 = 11$, $5 + 2 + 3 = 10$, $2 + 3 + 6 = 11$, $3 + 6 + 1 = 10$, $6 + 1 + 4 = 11$, any two numbers differ by at most $1$. On the right you can see an invalid arrangement: for example, $5 + 1 + 6 = 12$, and $3 + 2 + 4 = 9$, $9$ and $12$ differ more than by $1$.

 [Image] 


-----Input-----

The first and the only line contain one integer $n$ ($1 \le n \le 10^5$).


-----Output-----

If there is no solution, output "NO" in the first line. 

If there is a solution, output "YES" in the first line. In the second line output $2n$ numbers — numbers from $1$ to $2n$ in the order they will stay in the circle. Each number should appear only once. If there are several solutions, you can output any of them.


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

Output
YES
1 4 5 2 3 6 
Input
4

Output
NO


-----Note-----

Example from the statement is shown for the first example. 

It can be proved that there is no solution in the second example.
user: A group of n cities is connected by a network of roads. There is an undirected road between every pair of cities, so there are $\frac{n \cdot(n - 1)}{2}$ roads in total. It takes exactly y seconds to traverse any single road.

A spanning tree is a set of roads containing exactly n - 1 roads such that it's possible to travel between any two cities using only these roads.

Some spanning tree of the initial network was chosen. For every road in this tree the time one needs to traverse this road was changed from y to x seconds. Note that it's not guaranteed that x is smaller than y.

You would like to travel through all the cities using the shortest path possible. Given n, x, y and a description of the spanning tree that was chosen, find the cost of the shortest path that starts in any city, ends in any city and visits all cities exactly once.


-----Input-----

The first line of the input contains three integers n, x and y (2 ≤ n ≤ 200 000, 1 ≤ x, y ≤ 10^9).

Each of the next n - 1 lines contains a description of a road in the spanning tree. The i-th of these lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n) — indices of the cities connected by the i-th road. It is guaranteed that these roads form a spanning tree.


-----Output-----

Print a single integer — the minimum number of seconds one needs to spend in order to visit all the cities exactly once.


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

Output
9

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

Output
8



-----Note-----

In the first sample, roads of the spanning tree have cost 2, while other roads have cost 3. One example of an optimal path is $5 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2$.

In the second sample, we have the same spanning tree, but roads in the spanning tree cost 3, while other roads cost 2. One example of an optimal path is $1 \rightarrow 4 \rightarrow 5 \rightarrow 2 \rightarrow 3$.
user: Dreamoon likes coloring cells very much.

There is a row of $n$ cells. Initially, all cells are empty (don't contain any color). Cells are numbered from $1$ to $n$.

You are given an integer $m$ and $m$ integers $l_1, l_2, \ldots, l_m$ ($1 \le l_i \le n$)

Dreamoon will perform $m$ operations.

In $i$-th operation, Dreamoon will choose a number $p_i$ from range $[1, n-l_i+1]$ (inclusive) and will paint all cells from $p_i$ to $p_i+l_i-1$ (inclusive) in $i$-th color. Note that cells may be colored more one than once, in this case, cell will have the color from the latest operation.

Dreamoon hopes that after these $m$ operations, all colors will appear at least once and all cells will be colored. Please help Dreamoon to choose $p_i$ in each operation to satisfy all constraints.


-----Input-----

The first line contains two integers $n,m$ ($1 \leq m \leq n \leq 100\,000$).

The second line contains $m$ integers $l_1, l_2, \ldots, l_m$ ($1 \leq l_i \leq n$).


-----Output-----

If it's impossible to perform $m$ operations to satisfy all constraints, print "'-1" (without quotes).

Otherwise, print $m$ integers $p_1, p_2, \ldots, p_m$ ($1 \leq p_i \leq n - l_i + 1$), after these $m$ operations, all colors should appear at least once and all cells should be colored.

If there are several possible solutions, you can print any.


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

Output
2 4 1

Input
10 1
1

Output
-1
user: Vanya wants to minimize a tree. He can perform the following operation multiple times: choose a vertex v, and two disjoint (except for v) paths of equal length a_0 = v, a_1, ..., a_{k}, and b_0 = v, b_1, ..., b_{k}. Additionally, vertices a_1, ..., a_{k}, b_1, ..., b_{k} must not have any neighbours in the tree other than adjacent vertices of corresponding paths. After that, one of the paths may be merged into the other, that is, the vertices b_1, ..., b_{k} can be effectively erased: [Image] 

Help Vanya determine if it possible to make the tree into a path via a sequence of described operations, and if the answer is positive, also determine the shortest length of such path.


-----Input-----

The first line of input contains the number of vertices n (2 ≤ n ≤ 2·10^5).

Next n - 1 lines describe edges of the tree. Each of these lines contains two space-separated integers u and v (1 ≤ u, v ≤ n, u ≠ v) — indices of endpoints of the corresponding edge. It is guaranteed that the given graph is a tree.


-----Output-----

If it is impossible to obtain a path, print -1. Otherwise, print the minimum number of edges in a possible path.


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

Output
3

Input
7
1 2
1 3
3 4
1 5
5 6
6 7

Output
-1



-----Note-----

In the first sample case, a path of three edges is obtained after merging paths 2 - 1 - 6 and 2 - 4 - 5.

It is impossible to perform any operation in the second sample case. For example, it is impossible to merge paths 1 - 3 - 4 and 1 - 5 - 6, since vertex 6 additionally has a neighbour 7 that is not present in the corresponding path.
user: Sasha is taking part in a programming competition. In one of the problems she should check if some rooted trees are isomorphic or not. She has never seen this problem before, but, being an experienced participant, she guessed that she should match trees to some sequences and then compare these sequences instead of trees. Sasha wants to match each tree with a sequence a_0, a_1, ..., a_{h}, where h is the height of the tree, and a_{i} equals to the number of vertices that are at distance of i edges from root. 

Unfortunately, this time Sasha's intuition was wrong, and there could be several trees matching the same sequence. To show it, you need to write a program that, given the sequence a_{i}, builds two non-isomorphic rooted trees that match that sequence, or determines that there is only one such tree.

Two rooted trees are isomorphic, if you can reenumerate the vertices of the first one in such a way, that the index of the root becomes equal the index of the root of the second tree, and these two trees become equal.

The height of a rooted tree is the maximum number of edges on a path from the root to any other vertex.


-----Input-----

The first line contains a single integer h (2 ≤ h ≤ 10^5) — the height of the tree.

The second line contains h + 1 integers — the sequence a_0, a_1, ..., a_{h} (1 ≤ a_{i} ≤ 2·10^5). The sum of all a_{i} does not exceed 2·10^5. It is guaranteed that there is at least one tree matching this sequence.


-----Output-----

If there is only one tree matching this sequence, print "perfect".

Otherwise print "ambiguous" in the first line. In the second and in the third line print descriptions of two trees in the following format: in one line print $\sum_{i = 0}^{h} a_{i}$ integers, the k-th of them should be the parent of vertex k or be equal to zero, if the k-th vertex is the root.

These treese should be non-isomorphic and should match the given sequence.


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

Output
perfect

Input
2
1 2 2

Output
ambiguous
0 1 1 3 3
0 1 1 3 2



-----Note-----

The only tree in the first example and the two printed trees from the second example are shown on the picture:

$88$
user: You are given $n$ points on the plane. The polygon formed from all the $n$ points is strictly convex, that is, the polygon is convex, and there are no three collinear points (i.e. lying in the same straight line). The points are numbered from $1$ to $n$, in clockwise order.

We define the distance between two points $p_1 = (x_1, y_1)$ and $p_2 = (x_2, y_2)$ as their Manhattan distance: $$d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|.$$

Furthermore, we define the perimeter of a polygon, as the sum of Manhattan distances between all adjacent pairs of points on it; if the points on the polygon are ordered as $p_1, p_2, \ldots, p_k$ $(k \geq 3)$, then the perimeter of the polygon is $d(p_1, p_2) + d(p_2, p_3) + \ldots + d(p_k, p_1)$.

For some parameter $k$, let's consider all the polygons that can be formed from the given set of points, having any $k$ vertices, such that the polygon is not self-intersecting. For each such polygon, let's consider its perimeter. Over all such perimeters, we define $f(k)$ to be the maximal perimeter.

Please note, when checking whether a polygon is self-intersecting, that the edges of a polygon are still drawn as straight lines. For instance, in the following pictures:

 [Image] 

In the middle polygon, the order of points ($p_1, p_3, p_2, p_4$) is not valid, since it is a self-intersecting polygon. The right polygon (whose edges resemble the Manhattan distance) has the same order and is not self-intersecting, but we consider edges as straight lines. The correct way to draw this polygon is ($p_1, p_2, p_3, p_4$), which is the left polygon.

Your task is to compute $f(3), f(4), \ldots, f(n)$. In other words, find the maximum possible perimeter for each possible number of points (i.e. $3$ to $n$).


-----Input-----

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

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($-10^8 \leq x_i, y_i \leq 10^8$) — the coordinates of point $p_i$.

The set of points is guaranteed to be convex, all points are distinct, the points are ordered in clockwise order, and there will be no three collinear points.


-----Output-----

For each $i$ ($3\leq i\leq n$), output $f(i)$.


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

Output
12 14 
Input
3
0 0
0 2
2 0

Output
8 


-----Note-----

In the first example, for $f(3)$, we consider four possible polygons:   ($p_1, p_2, p_3$), with perimeter $12$.  ($p_1, p_2, p_4$), with perimeter $8$.  ($p_1, p_3, p_4$), with perimeter $12$.  ($p_2, p_3, p_4$), with perimeter $12$. 

For $f(4)$, there is only one option, taking all the given points. Its perimeter $14$.

In the second example, there is only one possible polygon. Its perimeter is $8$.
user: This is the easy version of the problem. The only difference between easy and hard versions is the constraint of $m$. You can make hacks only if both versions are solved.

Chiori loves dolls and now she is going to decorate her bedroom![Image] 

As a doll collector, Chiori has got $n$ dolls. The $i$-th doll has a non-negative integer value $a_i$ ($a_i < 2^m$, $m$ is given). Chiori wants to pick some (maybe zero) dolls for the decoration, so there are $2^n$ different picking ways.

Let $x$ be the bitwise-xor-sum of values of dolls Chiori picks (in case Chiori picks no dolls $x = 0$). The value of this picking way is equal to the number of $1$-bits in the binary representation of $x$. More formally, it is also equal to the number of indices $0 \leq i < m$, such that $\left\lfloor \frac{x}{2^i} \right\rfloor$ is odd.

Tell her the number of picking ways with value $i$ for each integer $i$ from $0$ to $m$. Due to the answers can be very huge, print them by modulo $998\,244\,353$.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 35$)  — the number of dolls and the maximum value of the picking way.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^m$)  — the values of dolls.


-----Output-----

Print $m+1$ integers $p_0, p_1, \ldots, p_m$  — $p_i$ is equal to the number of picking ways with value $i$ by modulo $998\,244\,353$.


-----Examples-----
Input
4 4
3 5 8 14

Output
2 2 6 6 0 
Input
6 7
11 45 14 9 19 81

Output
1 2 11 20 15 10 5 0