Problem Statement

There is a string S consisting of ( and ).

Taro and Jiro will play the following game using this string.

Taro goes first and Jiro goes second; they alternately choose and perform one of the following three types of operations:

• Delete the first character of S.
• Delete the last character of S.
• Declare termination.

The game ends when the length of S becomes exactly K, or when either player declares termination. At the end of the game, if S is a correct bracket sequence, Jiro wins; otherwise, Taro wins.

Given S before the game starts, determine the winner when both players act optimally.

You are given T test cases. Solve each of them.

Constraints

• 1 \le T \le 10^5
• 1 \le K < |S| \le 10^6
• S is a string consisting of ( and ).
• T and K are integers.
• The sum of |S| over all test cases is at most 10^6.

Sample Input 1

4
(()())
2
(())()
2
(()
2
(()()())((()()(())()))
12

Sample Output 1

Second
First
First
First

For the first test case, here is an example of how the game might proceed:

• Before the game starts, S is (()()).

• Taro deletes the first character of S, resulting in ()()).

• Next, Jiro deletes the last character of S, resulting in ()().

• Next, Taro deletes the last character of S, resulting in ()(.

• Next, Jiro deletes the last character of S, resulting in (), and the length of S becomes K=2, so the game ends.

• The final S is a correct bracket sequence, so Jiro wins.

In the third test case, for example, Taro can win by declaring termination on the first turn.

Problem Statement

For a string s consisting of lowercase English letters, let f(s) denote the number of substrings of s that are palindromes of even length. More precisely, f(s) is the number of pairs of integers l, r that satisfy all of the following conditions:

• 1 \leq l \leq r \leq |s|.
• r - l + 1 is even.
• s_l s_{l+1} \cdots s_{r} is a palindrome.

Given a string S consisting of lowercase English letters, output one string S' obtained by rearranging the characters of S such that f(S') is minimized.

You are given T test cases. Solve each of them.

Constraints

• 1 \le T \le 10^5
• 2 \le |S| \le 2 \times 10^5
• S consists of lowercase English letters.
• The sum of |S| over all test cases is at most 2 \times 10^5.

Sample Input 1

3
see
xxxxxy
abracadabra

Sample Output 1

ese
xxxyxx
abracadabra

For the first test case, the strings S' obtained by rearranging the characters of S are see, ese, and ees. Among these, only ese minimizes f(S'), so output it.

For the second test case, for example, outputting xxyxxx will also be considered correct.

Problem Statement

You are given positive integers N, X and integer sequences of length N: S = (S_1, S_2, \dots, S_N), P = (P_1, P_2, \dots, P_N). Here, each element of P is 1 or -1.

You are given Q queries. In each query, you are given integers l, r satisfying 1 \leq l \leq r \leq N, and you play the following game:

• Initially, your score is 0, and integers a, b are initialized as a = 1, b = 1.
• For i = l, l+1, \dots, r in this order, perform the following operation:
  • If i is even, replace the value of a with any integer between 1 and X (inclusive); if i is odd, replace the value of b with any integer between 1 and X (inclusive).
  • After that, if ab \geq S_i, add P_i to your score. Otherwise, the score does not change. Note that P_i can be negative.

For each query, find the maximum possible value of your score when the game ends.

Constraints

• 1 \le N, X, Q \le 10^5
• 1 \le S_i \le 10^5
• P_i = 1 or P_i = -1.
• For each query, 1 \le l \le r \le N.
• All input values are integers.

Sample Input 1

9 4 4
3 11 10 12 5 7 3 9 16
1 1 -1 1 -1 1 -1 1 1
5 9
1 4
5 5
2 8

Sample Output 1

2
3
0
1

In the first query, you can make the score 2 when the game ends by the following procedure:

It is impossible to make the score 3 or more when the game ends, so output 2.

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N. Each element is either an integer between 1 and N (inclusive) or -1.

Snuke has decided to create a new sequence using this sequence A.

First, replace all -1s in this sequence A with integers between 1 and N (inclusive).

Next, create a sequence B = (B_1, B_2, \ldots, B_N) of length N according to the following formula:

• B_i=A_{A_i}

Find the lexicographically smallest possible sequence B.

You are given T test cases. Solve each of them.

Constraints

• 1 \le T \le 10^5
• 1 \le N \le 5 \times 10^5
• 1 \le A_i \le N or A_i = -1.
• The sum of N over all test cases is at most 5\times 10^5.
• All input values are integers.

Sample Input 1

3
4
4 -1 -1 3
5
5 4 5 3 1
7
-1 6 5 -1 7 -1 6

Sample Output 1

3 1 4 1
1 3 1 5 5
1 1 7 1 6 1 1

In the first test case, the sequence A before Snuke's replacement is (4,-1,-1,3).

Suppose he replaces it to get A=(4, 3, 1, 3).

Then, B=(A_4, A_3, A_1, A_3)=(3, 1, 4, 1).

It is impossible to obtain a lexicographically smaller sequence B than this.

Problem Statement

Find the number, modulo 998244353, of strings S of length N consisting of A, B, C such that the following value equals K:

• The maximum length of a (not necessarily contiguous) subsequence of S that does not contain ABC as a (not necessarily contiguous) subsequence

You are given T test cases. Solve each of them.

Constraints

• 1 \le T \le 2 \times 10^5
• 1 \le N \le 10^6
• \max(0,N-100) \le K \le N

Sample Input 1

4
4 3
8 6
123 100
123456 123400

Sample Output 1

9
462
741573397
255048895

For the first test case, for example, ACBC satisfies the condition. ACBC itself contains ABC as a subsequence, and ACC does not contain ABC as a subsequence, so the maximum length of a subsequence that does not contain ABC as a subsequence is 3. Other examples that satisfy the condition include AABC and ABCA.