Description

A border of a string is a prefix that is also a suffix of the string but not the whole string. For example, the borders of abcababcab are ab and abcab.

Your task is to find all border lengths of a given string.

Input

The only input line has a string of length nnn consisting of characters a–z.

Constraints

• 1 ≤ n ≤ 10⁶

Output

Print all border lengths of the string in increasing order.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are two arrays a, b of length n, where a_i = i, i = 1, 2, ..., n. Also, you have another array c which is empty at the beginning.

Your task is to transform c into b, using the following operations:

1. Push the first element of a into the stack, and delete it in a
2. Append the top element of the stack to the last element of c, and pop it out of the stack

It is guaranteed that there always exists a series of operation that can transform c into b.

Input

The first line contains an integer n, representing the length of a and b. The second line contains n integers b₁, b₂, ..., b_n.

Constrain

• 1 <= n <= 1000
• 1 <= b_i <= n, i = 1, 2, ..., n
• If i ≠ j, b_i ≠ b_j

Output

Output 2n lines. If the i-th operation is the first type, output "Push" (without quote) in the i-th lines; otherwise, output "Pop" (without quote).

It can be shown that the seires of the operations are unique, and we always need 2n operations to complete the task.

Hint

For the sample testcase, the following shows the content of a, c, and stack after each operation:

Operation	a	c	stack
1	2, 3, 4		1
2	3, 4		1, 2
3	4		1, 2, 3
4	4	3	1, 2
5	4	3, 2	1
6		3, 2	1, 4
7		3, 2, 4	1
8		3, 2, 4, 1

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

DGL enjoys digging pits in a courtyard and filling them with water to create water pits. The courtyard is represented as a N x M matrix where each cell can be either a dirt mound "0" or a water pit "1". Water pit cells connected in any of the four directions (up, down, left, right) form a single water pit.

Your task is to:

1. Count the number of water pits.
2. Find the size of the largest water pit.

DGL will also specify changes to turn water pits into dirt mounds K times. Each change might disconnect water pits, affecting their size and count. You need to calculate the number of water pits and the largest water pit size after each change.

Input

The first line contains three integers N, M, and K.

The next N lines contain M integers (0, 1), representing the initial courtyard.

The next K lines contains 2 integers x, y, pair (x, y) representing a position to turn from a water pit into a dirt mound. Each specified position is guaranteed to be a water pit initially.

• 1 ≤ N * M ≤ 10⁶
• 1 ≤ K ≤ N * M
• 1 ≤ x ≤ N
• 1 ≤ y ≤ M

 

Hint

The test data for this problem is quite large, so if you're using C++ to solve it should include IO optimization in your program.

IO Optimization usage

remember to replace endl with '\n'.

#include<iostream>
...

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    /* write your code here*/
    
} 

Output

You need to print K + 1 line.

For the initial courtyard and each change, output two integers in one line seperate by a space:

1. The size of the largest water pit after the change.
2. The number of water pits after the change.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given string of length N, S consisting 'L' and 'R'.

Initally, array A contains one zero, that is A = [0].

Please perform the following sequentially for each of S_1, S₂, S₃, ...., S_n:

• If S_i is 'L' : Insert i to the left side of i-1.
• If S_i is 'R' : Insert i to the right side of i-1.

Find the final result of array A.

Input

The first line contains single integer, N.

The second line contains a string S consisting of 'L' and 'R'.

 

Constrain

• 0 < N ≤ 5 * 10⁵

Output

Print one line, content of array A.

Seperate the elements by space (do not print extra spaces after the last element).

Please add a newline('\n') at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss