Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N and positive integers P,Q,R, and S.
Here, P,Q,R, and S satisfy 1\leq P\leq Q<R\leq S \leq N and Q-P=S-R.

Let B=(B_1, B_2,\ldots, B_N) be the sequence obtained by swapping the P-th through Q-th terms and the R-th through S-th terms of A.
Print the sequence B.

Constraints

• 1\leq N \leq 100
• 1\leq A_i\leq 100
• 1\leq P\leq Q<R\leq S \leq N
• Q-P=S-R
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

5 6 7 4 1 2 3 8

Swapping the 1-st through 3-rd terms (1,2,3) and the 5-th through 7-th terms (5,6,7) of the sequence A=(1,2,3,4,5,6,7,8) results in B=(5,6,7,4,1,2,3,8), which should be printed with spaces in between.

Sample Input 2

5 2 3 4 5
2 2 1 1 1

Sample Output 2

2 1 1 2 1

The same integer may occur multiple times in the sequence.

Sample Input 3

2 1 1 2 2
50 100

Sample Output 3

100 50

Sample Input 4

10 2 4 7 9
22 75 26 45 72 81 47 29 97 2

Sample Output 4

22 47 29 97 72 81 75 26 45 2

Problem Statement

Takahashi is planning to eat N dishes.

The i-th dish he plans to eat is sweet if S_i = sweet, and salty if S_i = salty.

If he eats two sweet dishes consecutively, he will feel sick and be unable to eat any more dishes.

Determine whether he can eat all the dishes.

Constraints

• N is an integer between 1 and 100, inclusive.
• Each S_i is sweet or salty.

Sample Input 1

5
salty
sweet
salty
salty
sweet

Sample Output 1

Yes

He will not eat two sweet dishes consecutively, so he can eat all the dishes without feeling sick.

Sample Input 2

4
sweet
salty
sweet
sweet

Sample Output 2

Yes

He will feel sick but can still eat all the dishes.

Sample Input 3

6
salty
sweet
sweet
salty
sweet
sweet

Sample Output 3

No

He feels sick when eating the 3rd dish and cannot eat the 4th and subsequent dishes.

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N, each consisting of lowercase English letters. The lengths of these strings are all distinct.

Sort these strings in ascending order of length, and then concatenate them in that order to form a single string.

Constraints

• 2 \leq N \leq 50
• N is an integer.
• Each S_i is a string consisting of lowercase English letters with length between 1 and 50, inclusive.
• If i \neq j, the length of S_i is different from the length of S_j.

Sample Input 1

3
tc
oder
a

Sample Output 1

atcoder

When we sort (tc, oder, a) in ascending order of length, we get (a, tc, oder). Concatenating them in this order yields the string atcoder.

Sample Input 2

4
cat
enate
on
c

Sample Output 2

concatenate

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

• X is an N-digit positive integer.
• Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
  • 1 \le X_i \le 9 for all integers 1 \le i \le N;
  • |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

• N is an integer.
• 2 \le N \le 10^6

Sample Input 1

4

Sample Output 1

203

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

Problem Statement

Takahashi, who governs the Kingdom of AtCoder, has decided to change the alphabetical order of English lowercase letters.

The new alphabetical order is represented by a string X, which is a permutation of a, b, \ldots, z. The i-th character of X (1 \leq i \leq 26) would be the i-th smallest English lowercase letter in the new order.

The kingdom has N citizens, whose names are S_1, S_2, \dots, S_N, where each S_i (1 \leq i \leq N) consists of lowercase English letters.
Sort these names lexicographically according to the alphabetical order decided by Takahashi.

Constraints

• X is a permutation of a, b, \ldots, z.
• 2 \leq N \leq 50000
• N is an integer.
• 1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)
• S_i consists of lowercase English letters. (1 \leq i \leq N)
• S_i \neq S_j (1 \leq i \lt j \leq N)

Sample Input 1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

Sample Output 1

bzz
bzy
abx
caa

In the new alphabetical order set by Takahashi, b is smaller than a and z is smaller than y. Thus, sorting the citizens' names lexicographically would result in bzz, bzy, abx, caa in ascending order.

Sample Input 2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

Sample Output 2

b
a
ac
ab
abc

Problem Statement

This problem is a subproblem of Problem G.

A non-empty string S consisting of 0 and 1 is called a beautiful string when it satisfies the following condition:

• (Condition) You can perform the following sequence of operations until the length of S becomes 1 and make the only character remaining in S be 1.
  1. Choose any integer i satisfying 1 \leq i \leq |S| - 1.
  2. Define an integer x as follows:
     • If S_i = 0 and S_{i+1} = 0, let x = 1.
     • If S_i = 0 and S_{i+1} = 1, let x = 0.
     • If S_i = 1 and S_{i+1} = 0, let x = 0.
     • If S_i = 1 and S_{i+1} = 1, let x = 1.
  3. Remove S_i and S_{i+1}, and insert the digit corresponding to x in their place.
     For example, if S= 10101 and you choose i=2, the string after the operation is 1001.

You are given a string T of length N consisting of 0 and 1.
Find the number of beautiful strings that are substrings of T. Even if two substrings are identical as strings, count them separately if they are taken from different positions.

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an integer.
• T is a string of length N consisting of 0 and 1.

Sample Input 1

3
110

Sample Output 1

3

The string 11 obtained by taking the 1st through 2nd characters of T is a beautiful string, because if you choose i=1 and perform the operation, the string becomes 1. The beautiful strings that are substrings of T are the following three strings:

• The string 1 obtained by taking the 1st character of T.
• The string 1 obtained by taking the 2nd character of T.
• The string 11 obtained by taking the 1st through 2nd characters of T.

Sample Input 2

4
0000

Sample Output 2

4

Sample Input 3

30
011011100101110111100010011010

Sample Output 3

225

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N and an integer K.
There are 2^{N-1} ways to divide A into several contiguous subsequences. How many of these divisions have no subsequence whose elements sum to K? Find the count modulo 998244353.

Here, "to divide A into several contiguous subsequences" means the following procedure.

• Freely choose the number k (1 \leq k \leq N) of subsequences and an integer sequence (i_1, i_2, \dots, i_k, i_{k+1}) satisfying 1 = i_1 \lt i_2 \lt \dots \lt i_k \lt i_{k+1} = N+1.
• For each 1 \leq n \leq k, the n-th subsequence is formed by taking the i_n-th through (i_{n+1} - 1)-th elements of A, maintaining their order.

Here are some examples of divisions for A = (1, 2, 3, 4, 5):

• (1, 2, 3), (4), (5)
• (1, 2), (3, 4, 5)
• (1, 2, 3, 4, 5)

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^{15} \leq K \leq 10^{15}
• -10^9 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

3 3
1 2 3

Sample Output 1

2

There are two divisions that satisfy the condition in the problem statement:

• (1), (2, 3)
• (1, 2, 3)

Sample Input 2

5 0
0 0 0 0 0

Sample Output 2

0

Sample Input 3

10 5
-5 -1 -7 6 -6 -2 -5 10 2 -10

Sample Output 3

428

Problem Statement

There is a string S of length N consisting of lowercase English letters. Process a total of Q queries as follows:

• Type 1 : Change the i-th character of S to x.
• Type 2 : Let t be the substring of the current S from the l-th character through the r-th character. Find f(t) defined as follows for this string:
  • f(t) is the maximum length of consecutive identical characters in t.
  • More precisely, when choosing integers a,b such that 1 \le a \le b \le |t| and all characters from the a-th through the b-th character of t are equal, f(t) is the maximum possible value of b-a+1.
  • For example, f( aaaccbbbb )=4, f( bbaaabb )=3, f( x )=1.

Constraints

• N is an integer between 1 and 5 \times 10^5, inclusive.
• S is a string of length N consisting of lowercase English letters.
• Q is an integer between 1 and 5 \times 10^5, inclusive.
• Type 1 queries satisfy the following constraints:
  • i is an integer between 1 and N, inclusive.
  • x is a lowercase English letter.
• Type 2 queries satisfy the following constraints:
  • l,r are integers satisfying 1 \le l \le r \le N.

Sample Input 1

10 5
babaacczcc
2 1 4
1 3 a
2 1 10
1 8 c
2 1 10

Sample Output 1

1
4
5

This input contains five queries.

• Initially, the string S is babaacczcc.
• The 1st query is type 2 with l=1,r=4.
  • The extracted string is baba, and f( baba )=1.
• The 2nd query is type 1 with i=3,x= a.
  • The string S after the change is baaaacczcc.
• The 3rd query is type 2 with l=1,r=10.
  • The extracted string is baaaacczcc, and f( baaaacczcc )=4.
• The 4th query is type 1 with i=8,x= c.
  • The string S after the change is baaaaccccc.
• The 5th query is type 2 with l=1,r=10.
  • The extracted string is baaaaccccc, and f( baaaaccccc )=5.

Sample Input 2

1 1
a
1 1 z

Sample Output 2

The output may be empty.