amandeep603 / cses-question Goto Github PK

Given a string, your task is to determine the longest palindromic substring of the string. For example, the longest palindrome in aybabtu is bab.

Input
The only input line contains a string of length n. Each character is one of a–z.

Output
Print the longest palindrome in the string. If there are several solutions, you may print any of them.

Constraints
1≤n≤10^6

Example

Input:
aybabtu

Output:
bab

Your task is to divide the numbers 1,2,…,n into two sets of equal sum.

Input
The only input line contains an integer n.

Output
Print "YES", if the division is possible, and "NO" otherwise.

After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.

Constraints
1≤n≤10^ 6

Example 1
Input:

7
Output:
YES
4
1 2 4 7
3
3 5 6

Example 2
Input:
6
Output:
NO

Given a string, your task is to process operations where you cut a substring and paste it to the end of the string. What is the final string after all the operations?

Input
The first input line has two integers n and m: the length of the string and the number of operations. The characters of the string are numbered 1,2,…,n.

The next line has a string of length n that consists of characters A–Z.
Finally, there are m lines that describe the operations. Each line has two integers a and b: you cut a substring from position a to position b.

Output
Print the final string after all the operations.

Constraints
1≤n, m≤2⋅10^5
1≤a≤b≤n

Example

Input:
7 2
AYBABTU
3 5
3 5

Output:
AYABTUB

There is a street of length x whose positions are numbered 0,1,…,x. Initially there are no traffic lights, but n sets of traffic lights are added to the street one after another.

Your task is to calculate the length of the longest passage without traffic lights after each addition.

Input
The first input line contains two integers x and n: the length of the street and the number of sets of traffic lights.

Then, the next line contains n integers p1, p2 ,… ,…, pn : the position of each set of traffic lights. Each position is distinct.

Output
Print the length of the longest passage without traffic lights after each addition.

Constraints
1≤x≤10^9
1≤n≤2.10^5
0<pi<x

Example
Input:
8 3
3 6 2
Output:
5 3 3

Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows:
3→10→5→16→8→4→2→1

Your task is to simulate the execution of the algorithm for a given value of n.

Input
The only input line contains an integer n.

Output
Print a line that contains all values of n during the algorithm.

Constraints
1≤n≤10^6

Example
Input:
3
Output:
3 10 5 16 8 4 2 1