Problem Statement

There are N buildings arranged in a line at equal intervals. The height of the i-th building from the front is H_i.

You want to decorate some of these buildings with illuminations so that both of the following conditions are satisfied:

• The chosen buildings all have the same height.
• The chosen buildings are arranged at equal intervals.

What is the maximum number of buildings you can choose? If you choose exactly one building, it is considered to satisfy the conditions.

Constraints

• 1 \leq N \leq 3000
• 1 \leq H_i \leq 3000
• All input values are integers.

Sample Input 1

8
5 7 5 7 7 5 7 7

Sample Output 1

3

Choosing the 2nd, 5th, and 8th buildings from the front satisfies the conditions.

Sample Input 2

10
100 200 300 400 500 600 700 800 900 1000

Sample Output 2

1

Choosing just one building is considered to satisfy the conditions.

Sample Input 3

32
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5

Sample Output 3

3

Problem Statement

There are N people numbered from 1 to N.

Person i is wearing a bib with the number Q_i and is staring at person P_i.

For each i = 1,2,\ldots,N, find the number written on the bib of the person that the person wearing the bib with number i is staring at.

Constraints

• 2 \leq N \leq 3\times 10^5
• 1 \leq P_i \leq N
• The values of P_i are distinct.
• 1 \leq Q_i \leq N
• The values of Q_i are distinct.
• All input values are integers.

Sample Input 1

4
4 3 2 1
2 3 1 4

Sample Output 1

3 4 1 2

Person 3 is wearing the bib with the number 1, and the person that person 3 is staring at, person 2, is wearing the bib with the number 3. Thus, the answer for i = 1 is 3.

Sample Input 2

10
2 6 4 3 7 8 9 10 1 5
1 4 8 2 10 5 7 3 9 6

Sample Output 2

4 8 6 5 3 10 9 2 1 7

Problem Statement

Takahashi is trying to catch many Snuke.

There are five pits at coordinates 0, 1, 2, 3, and 4 on a number line, connected to Snuke's nest.

Now, N Snuke will appear from the pits. It is known that the i-th Snuke will appear from the pit at coordinate X_i at time T_i, and its size is A_i.

Takahashi is at coordinate 0 at time 0 and can move on the line at a speed of at most 1.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

• 1 \leq N \leq 10^5
• 0 < T_1 < T_2 < \ldots < T_N \leq 10^5
• 0 \leq X_i \leq 4
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 0 100
3 3 10
5 4 1

Sample Output 1

101

The optimal strategy is as follows.

• Wait at coordinate 0 to catch the first Snuke at time 1.
• Go to coordinate 4 to catch the third Snuke at time 5.

It is impossible to catch both the first and second Snuke, so this is the best he can.

Sample Input 2

3
1 4 1
2 4 1
3 4 1

Sample Output 2

0

Takahashi cannot catch any Snuke.

Sample Input 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

Sample Output 3

2978279323

Problem Statement

For a string S consisting of digits from 1 through 9, let f(S) be the string T obtained by the following procedure. (S_i denotes the i-th character of S.)

• Let T be an initially empty string.
• For i=1, 2, \dots, |S| - 1, perform the following operation:
  • Append n copies of S_i to the tail of T, where n is the value when S_{i+1} is interpreted as an integer.

For example, S = 313 yields f(S) = 3111 by the following steps.

• T is initially empty.
• For i=1, we have n = 1. Append one copy of 3 to T, which becomes 3.
• For i=2, we have n = 3. Append three copies of 1 to T, which becomes 3111.
• Terminate the procedure. We obtain T = 3111.

You are given a length-N string S consisting of digits from 1 through 9.
You repeat the following operation until the length of S becomes 1: replace S with f(S).
Find how many times, modulo 998244353, you perform the operation until you complete it. If you will repeat the operation indefinitely, print -1 instead.

Constraints

• 2 \leq N \leq 10^6
• S is a length-N string consisting of 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Sample Input 1

3
313

Sample Output 1

4

If S = 313, the length of S be comes 1 after four operations.

• We have f(S) = 3111. Replace S with 3111.
• We have f(S) = 311. Replace S with 311.
• We have f(S) = 31. Replace S with 31.
• We have f(S) = 3. Replace S with 3.
• Now that the length of S is 1, terminate the repetition.

Sample Input 2

9
123456789

Sample Output 2

-1

If S = 123456789, you indefinitely repeat the operation. In this case, -1 should be printed.

Sample Input 3

2
11

Sample Output 3

1

Problem Statement

You are given a string S = S_1 S_2 S_3 \dots S_{|S|} consisting of uppercase and lowercase English letters, (, and ).
The parentheses in the string S are properly matched.

Repeat the following operation until no more operations can be performed:

• First, select one pair of integers (l, r) that satisfies all of the following conditions:
  • l < r
  • S_l = (
  • S_r = )
  • Each of the characters S_{l+1}, S_{l+2}, \dots, S_{r-1} is an uppercase or lowercase English letter.
• Let T = \overline{S_{r-1} S_{r-2} \dots S_{l+1}}.
  • Here, \overline{x} denotes the string obtained by toggling the case of each character in x (uppercase to lowercase and vice versa).
• Then, delete the l-th through r-th characters of S and insert T at the position where the deletion occurred.

Refer to the sample inputs and outputs for clarification.

It can be proved that it is possible to remove all (s and )s from the string using the above operations, and the final string is independent of how and in what order the operations are performed.
Determine the final string.

Constraints

• 1 \le |S| \le 5 \times 10^5
• S consists of uppercase and lowercase English letters, (, and ).
• The parentheses in S are properly matched.

Sample Input 1

((A)y)x

Sample Output 1

YAx

Let us perform the operations for S = ((A)y)x.

• Choose l=2 and r=4. The substring (A) is removed and replaced with a.
  • After this operation, S = (ay)x.
• Choose l=1 and r=4. The substring (ay) is removed and replaced with YA.
  • After this operation, S = YAx.

After removing the parentheses, the string becomes YAx, which should be printed.

Sample Input 2

((XYZ)n(X(y)Z))

Sample Output 2

XYZNXYZ

Let us perform the operations for S = ((XYZ)n(X(y)Z)).

• Choose l=10 and r=12. The substring (y) is removed and replaced with Y.
  • After this operation, S = ((XYZ)n(XYZ)).
• Choose l=2 and r=6. The substring (XYZ) is removed and replaced with zyx.
  • After this operation, S = (zyxn(XYZ)).
• Choose l=6 and r=10. The substring (XYZ) is removed and replaced with zyx.
  • After this operation, S = (zyxnzyx).
• Choose l=1 and r=9. The substring (zyxnzyx) is removed and replaced with XYZNXYZ.
  • After this operation, S = XYZNXYZ.

After removing the parentheses, the string becomes XYZNXYZ, which should be printed.

Sample Input 3

(((()))(()))(())

Sample Output 3

The final outcome may be an empty string.

Sample Input 4

dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve

Sample Output 4

dFGsdccCrFNNnplCtQPOKjsiIwwEysAve