Problem Statement

You are given a string S of length N consisting of o and x, and integers L and R.

Determine whether all characters from the L-th through the R-th character of S are o.

Constraints

• 1\leq N \leq 100
• 1\leq L \leq R \leq N
• S is a string of length N consisting of o and x.
• N, L, and R are all integers.

Sample Input 1

10 6 8
xoxxooooxo

Sample Output 1

Yes

All characters from the 6-th through the 8-th character of S are o, so the answer is Yes.

Sample Input 2

9 6 8
xoxxoxoox

Sample Output 2

No

The 6-th character is x, so the answer is No.

Problem Statement

You are given a string S consisting of . and #.

Among all strings T that satisfy all of the following conditions, find one with the maximum number of os.

• The length of T is equal to the length of S.
• T consists of ., #, or o.
• T_i= # if and only if S_i= #.
• If T_i=T_j= o (i < j), then there exists at least one # among T_{i+1},\ldots,T_{j-1}.

Constraints

• S is a string consisting of . and # with length between 1 and 100, inclusive.

Sample Input 1

#..#.

Sample Output 1

#o.#o

Setting T= #o.#o satisfies all conditions.

There is no string T that satisfies all conditions and has more than two os, so outputting #o.#o is correct.

Outputting #.o#o is also correct.

Sample Input 2

#

Sample Output 2

#

Sample Input 3

.....

Sample Output 3

..o..

Outputting o...., .o..., ...o., or ....o is also correct.

Sample Input 4

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

Sample Output 4

o..#.o#o##o#o

Problem Statement

You are given N strings S_1,\ldots,S_N.

For a sequence (A_1,\ldots,A_K) of length K where all elements are between 1 and N, inclusive, define the string f(A_1,\ldots,A_K) as S_{A_1}+S_{A_2}+\dots+S_{A_K}. Here, + represents string concatenation.

When all f(A_1,\dots,A_K) for the N^K sequences are sorted in lexicographical order, find the X-th smallest string.

Constraints

• 1\leq N \leq 10
• 1\leq K \leq 5
• 1\leq X \leq N^K
• S_i is a string consisting of lowercase English letters with length at most 10.
• N, K, and X are all integers.

Sample Input 1

3 2 6
abc
xxx
abc

Sample Output 1

abcxxx

• f(1,1)= abcabc
• f(1,2)= abcxxx
• f(1,3)= abcabc
• f(2,1)= xxxabc
• f(2,2)= xxxxxx
• f(2,3)= xxxabc
• f(3,1)= abcabc
• f(3,2)= abcxxx
• f(3,3)= abcabc

When these are sorted in lexicographical order: abcabc, abcabc, abcabc, abcabc, abcxxx, abcxxx, xxxabc, xxxabc, xxxxxx, the 6-th is abcxxx.

Sample Input 2

5 5 416
a
aa
aaa
aa
a

Sample Output 2

aaaaaaa

Problem Statement

You are given length-N sequences A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N) consisting of non-negative integers, and a positive integer M.

When you can freely rearrange the elements of A, find the minimum possible value of \displaystyle \sum_{i=1}^N \left((A_i+B_i) \bmod M\right).

T test cases are given, so find the answer for each of them.

Constraints

• 1\le T \le 10^5
• 1\le N\le 3\times 10^5
• 1\le M\le 10^9
• 0\le A_i,B_i < M
• The sum of N over all test cases is at most 3\times 10^5.
• All input values are integers.

Sample Input 1

3
3 6
3 1 4
2 0 1
1 1000000000
999999999
999999999
10 201
144 150 176 154 110 187 38 136 111 46
96 109 73 63 85 1 156 7 13 171

Sample Output 1

5
999999998
619

For the first test case, if we rearrange A as 4,3,1, then (A_i+B_i)\bmod M becomes 0,3,2, respectively, and their sum is 5.

Problem Statement

AtCoder Country has N cities numbered from 1 to N, M roads, and K airports.

The i-th road connects cities A_i and B_i bidirectionally and takes C_i hours to travel. There are airports in cities D_1,\ldots,D_K, and you can travel between cities with airports in T hours.

Process Q queries in order. Each query is one of the following three types:

• 1 x y t: A road connecting cities x and y bidirectionally in t hours is built.
• 2 x: An airport is built in city x.
• 3: Let f(x,y) be the smallest number of hours needed to reach city y from city x using roads and airports if reachable, and 0 if unreachable. Find \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y).

Constraints

• 1 \leq N \leq 500
• 0 \leq M \leq 10^5
• 1 \leq A_i < B_i \leq N
• 1 \leq C_i \leq 10^9
• 0 \leq K \leq N
• 1 \leq T \leq 10^9
• 1 \leq D_1 < \dots < D_K \leq N
• 1 \leq Q \leq 1000
• For type 1 queries: 1\leq x < y \leq N, 1 \leq t \leq 10^9.
• For type 2 queries: 1 \leq x \leq N.
• All input values are integers.

Sample Input 1

4 1
1 2 10
2 100
1 3
5
3
1 2 3 60
3
2 4
3

Sample Output 1

440
280
900

AtCoder Country has four cities. Initially, there is a road connecting cities 1 and 2 in 10 hours, and airports connecting cities 1 and 3 in 100 hours.

• Initially, f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=100, f(2,3)=f(3,2)=110, and others are 0, so \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=440.
• A new road connecting cities 2 and 3 in 60 hours is built.
• f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=70, f(2,3)=f(3,2)=60, and others are 0, so \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=280.
• A new airport is built in city 4.
• f(1,2)=f(2,1)=10, f(1,3)=f(3,1)=70, f(1,4)=f(4,1)=100, f(2,3)=f(3,2)=60, f(2,4)=f(4,2)=110, f(3,4)=f(4,3)=100, and others are 0, so \sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)=900.

Multiple roads may exist between some pair of cities. Also, a city may have multiple airports.

Problem Statement

You are given a tree T with N vertices numbered from 1 to N, and an integer K. The i-th edge (1\le i\le N - 1) connects vertices U_i and V_i. Also, vertex i (1\le i\le N) has an integer A_i written on it. Initially, all vertices are colored white.

You perform the following action at least 0 times and at most K times:

• Choose a path in tree T such that all vertices on the path are colored white. Then, color all vertices on the chosen path black.

Find the maximum possible sum of integers written on vertices that are colored black after finishing the actions.

Constraints

• 2\le N\le 2\times 10^5
• 1\le K\le 5
• 1\le A_i\le 10^9
• 1\le U_i < V_i \le N
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

13

If you choose the path with vertices 3 and 4 as endpoints, you can color vertices 1,3,4 black. In this case, the sum of integers written on the colored vertices is 1+4+8=13.

You cannot make the sum of integers written on black vertices greater than 13, so output 13.

Sample Input 2

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

Sample Output 2

27

For example, you can make the sum of integers written on black vertices 27 by performing operations as follows:

• Choose the path with vertices 4 and 5 as endpoints. Color vertices 2,4,5 black.
• Choose the path with vertices 6 and 7 as endpoints. Color vertices 3,6,7 black.

You cannot make the sum of integers written on black vertices greater than 27, so output 27.

Sample Input 3

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

Sample Output 3

52

Problem Statement

You are given N strings S_1,\ldots,S_N.

For a sequence (A_1,\ldots,A_K) of length K where all elements are between 1 and N, inclusive, define the string f(A_1,\ldots,A_K) as S_{A_1}+S_{A_2}+\dots+S_{A_K}. Here, + represents string concatenation.

Among all f(A_1,\dots,A_K) for the N^K sequences, find the lexicographically smallest string.

Constraints

• 1\leq N \leq 10^5
• 1\leq K \leq 10^5
• S_i is a string consisting of lowercase English letters with length at most 10.
• N and K are integers.

Sample Input 1

3 2
abc
xxx
abc

Sample Output 1

abcabc

• f(1,1)= abcabc
• f(1,2)= abcxxx
• f(1,3)= abcabc
• f(2,1)= xxxabc
• f(2,2)= xxxxxx
• f(2,3)= xxxabc
• f(3,1)= abcabc
• f(3,2)= abcxxx
• f(3,3)= abcabc

Among these, the lexicographically smallest is abcabc.

Sample Input 2

4 3
abcd
abc
ab
a

Sample Output 2

aaa

Sample Input 3

3 2
cba
cb
c

Sample Output 3

cbac