Problem Statement

In the Kingdom of AtCoder, a week consists of A+B days, with the first through A-th days being holidays and the (A+1)-th through (A+B)-th being weekdays.

Takahashi has N plans, and the i-th plan is scheduled D_i days later.

He has forgotten what day of the week it is today. Determine if it is possible for all of his N plans to be scheduled on holidays.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq A,B\leq 10^9
• 1\leq D_1<D_2<\ldots<D_N\leq 10^9

Sample Input 1

3 2 5
1 2 9

Sample Output 1

Yes

In this input, a week consists of seven days, with the first through second days being holidays and the third through seventh days being weekdays.

Let us assume today is the seventh day of the week. In this case, one day later would be the first day of the week, two days later would be the second day of the week, and nine days later would also be the second day of the week, making all plans scheduled on holidays. Therefore, it is possible for all of Takahashi's N plans to be scheduled on holidays.

Sample Input 2

2 5 10
10 15

Sample Output 2

No

Sample Input 3

4 347 347
347 700 705 710

Sample Output 3

Yes

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S equal T by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in S, insert a character equal to these characters. That is, take the following three steps.

1. Let N be the current length of S, and S = S_1S_2\ldots S_N.
2. Choose an integer i between 1 and N-1 (inclusive) such that S_i = S_{i+1}. (If there is no such i, do nothing and terminate the operation now, skipping step 3.)
3. Insert a single copy of the character S_i(= S_{i+1}) between the i-th and (i+1)-th characters of S. Now, S is a string of length N+1: S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N.

Constraints

• Each of S and T is a string of length between 2 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

abbaac
abbbbaaac

Sample Output 1

Yes

You can make S = abbaac equal T = abbbbaaac by the following three operations.

• First, insert b between the 2-nd and 3-rd characters of S. Now, S = abbbaac.
• Next, insert b again between the 2-nd and 3-rd characters of S. Now, S = abbbbaac.
• Lastly, insert a between the 6-th and 7-th characters of S. Now, S = abbbbaaac.

Thus, Yes should be printed.

Sample Input 2

xyzz
xyyzz

Sample Output 2

No

No sequence of operations makes S = xyzz equal T = xyyzz. Thus, No should be printed.

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

You are given N strings consisting of lowercase English letters. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

For two strings x and y, \mathrm{LCP}(x, y) is defined to be the maximum integer n that satisfies all of the following conditions:

• The lengths of x and y are both at least n.
• For all integers i between 1 and n, inclusive, the i-th character of x and that of y are equal.

Find the following value for all i = 1, 2, \dots, N:

• \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)

Constraints

• 2 \leq N \leq 5 \times 10^5
• N is an integer.
• S_i is a string of length at least 1 consisting of lowercase English letters (i = 1, 2, \dots, N).
• The sum of lengths of S_i is at most 5 \times 10^5.

Sample Input 1

3
abc
abb
aac

Sample Output 1

2
2
1

\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1, and \mathrm{LCP}(S_2, S_3) = 1.

Sample Input 2

11
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a

Sample Output 2

4
3
2
1
0
1
0
4
3
2
1

Problem Statement

Given is an undirected graph with N+1 vertices.
The vertices are called Vertex 0, Vertex 1, \ldots, Vertex N.

For each i=1,2,\ldots,N, the graph has an undirected edge with a weight of A_i connecting Vertex 0 and Vertex i.

Additionally, for each i=1,2,\ldots,N, the graph has an undirected edge with a weight of B_i connecting Vertex i and Vertex i+1. (Here, Vertex N+1 stands for Vertex 1.)

The graph has no edge other than these 2N edges above.

Let us delete some of the edges from this graph so that the graph will be bipartite.
What is the minimum total weight of the edges that have to be deleted?

Constraints

• 3 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• All values in input are integers.

Sample Input 1

5
31 4 159 2 65
5 5 5 5 10

Sample Output 1

16

Deleting the edge connecting Vertices 0,2 (weight: 4), the edge connecting Vertices 0,4 (weight: 2), and the edge connecting Vertices 1,5 (weight: 10) makes the graph bipartite.

Sample Input 2

4
100 100 100 1000000000
1 2 3 4

Sample Output 2

10