Problem Statement

You are given a string S consisting of lowercase English letters.

Swap the a-th and b-th characters from the beginning of S and print the resulting string.

Constraints

• S is a string consisting of lowercase English letters.
• The length of S, |S|, satisfies 2 \leq |S| \leq 10.
• 1 \leq a < b \leq |S|
• a and b are integers.

Sample Input 1

chokudai
3 5

Sample Output 1

chukodai

After swapping the 3-rd character o and 5-th character u of chokudai, we have chukodai.

Sample Input 2

aa
1 2

Sample Output 2

aa

In this sample, after swapping the 1-st and 2-nd characters of S, we have the same string as S.

Sample Input 3

aaaabbbb
1 8

Sample Output 3

baaabbba

Problem Statement

We have 4 cards with an integer 1 written on it, 4 cards with 2, \ldots, 4 cards with N, for a total of 4N cards.

Takahashi shuffled these cards, removed one of them, and gave you a pile of the remaining 4N-1 cards. The i-th card (1 \leq i \leq 4N - 1) of the pile has an integer A_i written on it.

Find the integer written on the card removed by Takahashi.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq N \, (1 \leq i \leq 4N - 1)
• For each k \, (1 \leq k \leq N), there are at most 4 indices i such that A_i = k.
• All values in input are integers.

Sample Input 1

3
1 3 2 3 3 2 2 1 1 1 2

Sample Output 1

3

Takahashi removed a card with 3 written on it.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

4
3 2 1 1 2 4 4 4 4 3 1 3 2 1 3

Sample Output 3

2

Problem Statement

There are N stations on a certain line operated by AtCoder Railway. The i-th station (1 \leq i \leq N) from the starting station is named S_i.

Local trains stop at all stations, while express trains may not. Specifically, express trains stop at only M \, (M \leq N) stations, and the j-th stop (1 \leq j \leq M) is the station named T_j.
Here, it is guaranteed that T_1 = S_1 and T_M = S_N, that is, express trains stop at both starting and terminal stations.

For each of the N stations, determine whether express trains stop at that station.

Constrains

• 2 \leq M \leq N \leq 10^5
• N and M are integers.
• S_i (1 \leq i \leq N) is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
• S_i \neq S_j \, (i \neq j)
• T_1 = S_1 and T_M = S_N.
• (T_1, \dots, T_M) is obtained by removing zero or more strings from (S_1, \dots, S_N) and lining up the remaining strings without changing the order.

Sample Input 1

5 3
tokyo kanda akiba okachi ueno
tokyo akiba ueno

Sample Output 1

Yes
No
Yes
No
Yes

Sample Input 2

7 7
a t c o d e r
a t c o d e r

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes
Yes

Express trains may stop at all stations.

Problem Statement

2N people numbered 1, 2, \ldots, 2N attend a ball. They will group into N pairs and have a dance.

If Person i and Person j pair up, where i is smaller than j, the affinity of that pair is A_{i, j}.
If the N pairs have the affinity of B_1, B_2, \ldots, B_N, the total fun of the ball is the bitwise XOR of them: B_1 \oplus B_2 \oplus \cdots \oplus B_N.

Print the maximum possible total fun of the ball when the 2N people can freely group into N pairs.

Constraints

• 1 \leq N \leq 8
• 0 \leq A_{i, j} < 2^{30}
• All values in input are integers.

Sample Input 1

2
4 0 1
5 3
2

Sample Output 1

6

Let \lbrace i, j\rbrace denote a pair of Person i and Person j. There are three ways for the four people to group into two pairs, as follows.

• Group into \lbrace 1, 2\rbrace, \lbrace 3, 4\rbrace. The total fun of the ball here is A_{1, 2} \oplus A_{3, 4} = 4 \oplus 2 = 6.
• Group into \lbrace 1, 3\rbrace, \lbrace 2, 4\rbrace. The total fun of the ball here is A_{1, 3} \oplus A_{2, 4} = 0 \oplus 3 = 3.
• Group into \lbrace 1, 4\rbrace, \lbrace 2, 3\rbrace. The total fun of the ball here is A_{1, 4} \oplus A_{2, 3} = 1 \oplus 5 = 4.

Therefore, the maximum possible total fun of the ball is 6.

Sample Input 2

1
5

Sample Output 2

5

There will be just a pair of Person 1 and Person 2, where the total fun of the ball is 5.

Sample Input 3

5
900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467
369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136
138172503 571268336 111747377 595746631 934427285 840101927 757856472
655483844 580613112 445614713 607825444 252585196 725229185
827291247 105489451 58628521 1032791417 152042357
919691140 703307785 100772330 370415195
666350287 691977663 987658020
1039679956 218233643
70938785

Sample Output 3

1073289207

Problem Statement

We have N cards. The i-th card (1 \leq i \leq N) has an integer A_i written on it.

Takahashi will choose any number of cards from these. However, for each i (1 \leq i \leq N - 1), at least one of the i-th and (i+1)-th cards must be chosen.

Find the following values.

• The maximum possible average of the integers written on the chosen cards
• The maximum possible median of the integers written on the chosen cards

Here, the median of the n integers is defined to be the \lceil \frac{n}{2} \rceil-th smallest of them, where \lceil x \rceil is the smallest integer not less than x.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq A_i \leq 10^{9}
• All values in input are integers.

Sample Input 1

6
2 1 2 1 1 10

Sample Output 1

4
2

Choosing the 2-nd, 4-th, and 6-th cards makes the average of the written integers \frac{12}{3} = 4, which is the maximum possible.

Choosing the 1-st, 3-rd, 5-th, and 6-th cards makes the median of the written integers 2, which is the maximum possible.

Sample Input 2

7
3 1 4 1 5 9 2

Sample Output 2

5.250000000
4

For the average, your output may contain some degree of error: for example, the output 5.2491 is still considered correct. For the median, however, the exact value must be printed.

Problem Statement

The shop supaisu-ya sells 2^N-1 kinds of spices: Spice 1, Spice 2, \ldots, Spice 2^N-1. One pack of each spice is in stock. For each i = 1, 2, \ldots, 2^N-1, Spice i costs c_i yen. Takahashi can buy any of these spices.

He plans to make curry after getting home by choosing one or more of the bought spices and mixing them.
If k spices, Spice A_1, Spice A_2, \ldots, Spice A_k, are mixed, the hotness of the resulting curry is A_1 \oplus A_2 \oplus \cdots \oplus A_k, where \oplus denotes the bitwise XOR.

Takahashi wants to decide the hotness of the curry based on his feeling after getting home. For now, he will buy a set of spices that allows him to make curry of any hotness from 1 through 2^N-1. Print the minimum possible amount of money Takahashi pays.

Constraints

• 2 \leq N \leq 16
• 1 \leq c_i \leq 10^9
• All values in input are integers.

Sample Input 1

2
4 5 3

Sample Output 1

7

If Takahashi buys Spice 1 and 3, he can make curry of any hotness from 1 through 3, as follows.

• To make curry of hotness 1, use just Spice 1.
• To make curry of hotness 2, mix Spice 1 and Spice 3.
• To make curry of hotness 3, use just Spice 3.

Here, Takahashi pays c_1 + c_3 = 4 + 3 = 7 yen, which is the minimum possible amount he pays.

Sample Input 2

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

Sample Output 2

15

Problem Statement

We have a directed graph with N vertices. The N vertices are called Vertex 1, Vertex 2, \ldots, Vertex N. At time 0, the graph has no edge.

For each t = 1, 2, \ldots, T, at time t, a directed edge from Vertex u_t to Vertex v_t will be added. (The edge may be a self-loop, that is, u_t = v_t may hold.)

A vertex is called good when it can be reached by starting at Vertex 1 and traversing an edge exactly L times.

For each i = 1, 2, \ldots, N, print the earliest time when Vertex i is good. If there is no time when Vertex i is good, print -1 instead.

Constraints

• 2 \leq N \leq 100
• 1 \leq T \leq N^2
• 1 \leq L \leq 10^9
• 1 \leq u_t, v_t \leq N
• i \neq j \Rightarrow (u_i, v_i) \neq (u_j, v_j)
• All values in input are integers.

Sample Input 1

4 5 3
2 3
3 4
1 2
3 2
2 2

Sample Output 1

-1 4 5 3

At time 0, the graph has no edge. Afterward, edges are added as follows.

• At time 1, a directed edge from Vertex 2 to Vertex 3 is added.
• At time 2, a directed edge from Vertex 3 to Vertex 4 is added.
• At time 3, a directed edge from Vertex 1 to Vertex 2 is added. Now, Vertex 4 can be reached from Vertex 1 in exactly three moves: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4, making Vertex 4 good.
• At time 4, a directed edge from Vertex 3 to Vertex 2 is added. Now, Vertex 2 can be reached from Vertex 1 in exactly three moves: 1 \rightarrow 2 \rightarrow 3 \rightarrow 2, making Vertex 2 good.
• At time 5, a directed edge (self-loop) from Vertex 2 to Vertex 2 is added. Now, Vertex 3 can be reached from Vertex 1 in exactly three moves: 1 \rightarrow 2 \rightarrow 2 \rightarrow 3, making Vertex 3 good.

Vertex 1 will never be good.

Sample Input 2

2 1 1000000000
1 2

Sample Output 2

-1 -1

Problem Statement

Given are positive integers N, M, and a sequence of positive integers D = (D_1, \dots, D_N).

Find the number of sequences of positive integers A = (A_1, \dots, A_N) that satisfy the following conditions, modulo 998244353.

• 1 \leq A_i \leq M \, (1 \leq i \leq N)
• A_i \neq A_j \, (1 \leq i \lt j \leq N)
• For each i \, (1 \leq i \leq N), A_i is a multiple of D_i.

Constraints

• 2 \leq N \leq 16
• 1 \leq M \leq 10^{18}
• 1 \leq D_i \leq M \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

3 7
2 3 4

Sample Output 1

3

The three sequences A that satisfy the conditions are (2, 3, 4), (2, 6, 4), (6, 3, 4).

Sample Input 2

3 3
1 2 2

Sample Output 2

0

No sequence A satisfies the conditions.

Sample Input 3

6 1000000000000000000
380214083 420492929 929717250 666796775 209977152 770361643

Sample Output 3

325683519

Be sure to find the count modulo 998244353.