Problem Statement

Takahashi is a teapot.
Since he is a teapot, he will gladly accept tea, but will refuse any other liquid.
Determine whether you can pour a liquid named S into him.

You are given a string S of length N consisting of lowercase English letters.
Determine whether S is a string that ends with tea.

Constraints

• 1 \leq N \leq 20
• N is an integer.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

8
greentea

Sample Output 1

Yes

greentea is a string that ends with tea.

Sample Input 2

6
coffee

Sample Output 2

No

coffee is not a string that ends with tea.

Sample Input 3

3
tea

Sample Output 3

Yes

Sample Input 4

1
t

Sample Output 4

No

Problem Statement

You are given a string S of length 3.
Print a character that occurs only once in S.
If there is no such character, print -1 instead.

Constraints

• S is a string of length 3 consisting of lowercase English letters.

Sample Input 1

pop

Sample Output 1

o

o occurs only once in pop.

Sample Input 2

abc

Sample Output 2

a

a, b, and c occur once each in abc, so you may print any of them.

Sample Input 3

xxx

Sample Output 3

-1

No character occurs only once in xxx.

Problem Statement

There are 2N people standing in a row, and the person at the i-th position from the left is wearing clothes of color A_i. Here, the clothes have N colors from 1 to N, and exactly two people are wearing clothes of each color.

Find how many of the integers i=1,2,\ldots,N satisfy the following condition:

• There is exactly one person between the two people wearing clothes of color i.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq N
• Each integer from 1 through N appears exactly twice in A.
• All input values are integers.

Sample Input 1

3
1 2 1 3 2 3

Sample Output 1

2

There are two values of i that satisfy the condition: 1 and 3.

In fact, the people wearing clothes of color 1 are at the 1st and 3rd positions from the left, with exactly one person in between.

Sample Input 2

2
1 1 2 2

Sample Output 2

0

There may be no i that satisfies the condition.

Sample Input 3

4
4 3 2 3 2 1 4 1

Sample Output 3

3

Problem Statement

Takahashi aggregated usage records from ticket gates. However, he accidentally erased some records of entering and exiting stations. He is trying to restore the erased records.

You are given a string S consisting of i and o. We want to insert zero or more characters at arbitrary positions in S so that the resulting string satisfies the following conditions:

• Its length is even, and every odd-numbered (1st, 3rd, ...) character is i while every even-numbered (2nd, 4th, ...) character is o.

Find the minimum number of characters that need to be inserted. It can be proved under the constraints of this problem that by inserting an appropriate finite number of characters, S can be made to satisfy the conditions.

Constraints

• S is a string of length between 1 and 100, consisting of i and o.

Sample Input 1

ioi

Sample Output 1

1

We can insert o after the 3rd character to form ioio to satisfy the conditions. The conditions cannot be satisfied by inserting zero or fewer characters.

Sample Input 2

iioo

Sample Output 2

2

We can insert o after the 1st character and i after the 3rd character to satisfy the conditions. The conditions cannot be satisfied by inserting one or fewer characters.

Sample Input 3

io

Sample Output 3

0

S already satisfies the conditions.

Problem Statement

For a non-negative integer K, we define a level-K carpet as follows:

• A level-0 carpet is a 1 \times 1 grid consisting of a single black cell.
• For K > 0, a level-K carpet is a 3^K \times 3^K grid. When this grid is divided into nine 3^{K-1} \times 3^{K-1} blocks:
  • The central block consists entirely of white cells.
  • The other eight blocks are level-(K-1) carpets.

You are given a non-negative integer N.
Print a level-N carpet according to the specified format.

Constraints

• 0 \leq N \leq 6
• N is an integer.

Sample Input 1

1

Sample Output 1

###
#.#
###

A level-1 carpet is a 3 \times 3 grid as follows:

When output according to the specified format, it looks like the sample output.

Sample Input 2

2

Sample Output 2

#########
#.##.##.#
#########
###...###
#.#...#.#
###...###
#########
#.##.##.#
#########

A level-2 carpet is a 9 \times 9 grid.

Problem Statement

You are given two integer sequences A and B, each of length N. Choose integers i, j (1 \leq i, j \leq N) to maximize the value of A_i + B_j.

Constraints

• 1 \leq N \leq 5 \times 10^5
• |A_i| \leq 10^9 (i=1,2,\dots,N)
• |B_j| \leq 10^9 (j=1,2,\dots,N)
• All input values are integers.

Sample Input 1

2
-1 5
3 -7

Sample Output 1

8

For (i,j) = (1,1), (1,2), (2,1), (2,2), the values of A_i + B_j are 2, -8, 8, -2 respectively, and (i,j) = (2,1) achieves the maximum value 8.

Sample Input 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

Sample Output 2

33

Problem Statement

You are given a string S of length N consisting of 0 and 1.

You can perform the following operation on S any number of times (possibly zero):

• Delete the first or last character, flip it (change 0 to 1 or 1 to 0), and insert it back at any position. More formally, let r(0)= 1 and r(1)= 0, and perform one of the following: (Here, S_i denotes the i-th character of S.)
  • Choose any i\ (1\leq i\leq N) and change S to S_2\dots S_i\,r(S_1)\,S_{i+1}\dots S_N.
  • Choose any i\ (0\leq i\leq N-1) and change S to S_1\dots S_i\,r(S_N)\,S_{i+1}\dots S_{N-1}.

Find the minimum number of operations required to make all characters of S the same. It can be proved that such a sequence of operations always exists.

You are given T test cases, so solve each of them.

Constraints

• 1\leq T\leq 2\times 10^5
• 2\leq N \leq 5\times 10^5
• T and N are integers.
• S is a string of length N consisting of 0 and 1.
• The sum of N over all test cases is at most 5\times 10^5.

Sample Input 1

3
5
01001
3
000
15
110010111100101

Sample Output 1

4
0
16

For the first test case, for example, you can make all characters of S into 0 with four operations as follows. It is impossible to make all characters of S the same with three or fewer operations, so the answer is 4.

• Delete the first character 0, and insert 1 between the 1st and 2nd characters (in S after deletion). S becomes 11001.
• Delete the first character 1, and insert 0 between the 2nd and 3rd characters (in S after deletion). S becomes 10001.
• Delete the last character 1, and insert 0 at the end (in S after deletion). S becomes 10000.
• Delete the first character 1, and insert 0 at the beginning (in S after deletion). S becomes 00000.

For the second test case, all characters of S are the same from the beginning, so no operation is needed.

Problem Statement

We have a variable X and N kinds of operations that change the value of X. Operation i is represented as a pair of integers (T_i,A_i), and is the following operation:

• if T_i=1, it replaces the value of X with X\ {\rm and}\ A_i;
• if T_i=2, it replaces the value of X with X\ {\rm or}\ A_i;
• if T_i=3, it replaces the value of X with X\ {\rm xor}\ A_i.

Initialize X with the value of C and execute the following procedures in order:

• Perform Operation 1, and then print the resulting value of X.
• Next, perform Operation 1, 2 in this order, and then print the value of X.
• Next, perform Operation 1, 2, 3 in this order, and then print the value of X.
• \vdots
• Next, perform Operation 1, 2, \ldots, N in this order, and then print the value of X.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1\leq T_i \leq 3
• 0\leq A_i \lt 2^{30}
• 0\leq C \lt 2^{30}
• All values in input are integers.

Sample Input 1

3 10
3 3
2 5
1 12

Sample Output 1

9
15
12

The initial value of X is 10.

• Operation 1 changes X to 9.
• Next, Operation 1 changes X to 10, and then Operation 2 changes it to 15.
• Next, Operation 1 changes X to 12, and then Operation 2 changes it to 13, and then Operation 3 changes it to 12.

Sample Input 2

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

Sample Output 2

0
2
1
0
5
3
3
11
2

Problem Statement

You are given positive integers N, K, and an integer sequence of length N: A = (A_1, A_2, \dots, A_N).

Find \displaystyle \sum_{1\leq l\leq r\leq N} \Bigg(\sum_{l\leq i\leq r} A_i\Bigg)^K, modulo 998244353.

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq K \leq 10
• 0 \leq A_i < 998244353
• All input values are integers.

Sample Input 1

3 2
3 1 2

Sample Output 1

75

The value is A_1^2+A_2^2+A_3^2+(A_1+A_2)^2+(A_2+A_3)^2+(A_1+A_2+A_3)^2=3^2+1^2+2^2+4^2+3^2+6^2=75.

Sample Input 2

1 10
0

Sample Output 2

0

Sample Input 3

10 5
91 59 85 60 57 72 12 3 27 16

Sample Output 3

428633385

Be sure to find the sum modulo 998244353.