Problem Statement

You are given integers A and B between 0 and 255 (inclusive). Find a non-negative integer C such that A \text{ xor }C=B.

It can be proved that there uniquely exists such C, and it will be between 0 and 255 (inclusive).

Constraints

• 0\leq A,B \leq 255
• All values in input are integers.

Sample Input 1

3 6

Sample Output 1

5

When written in binary, 3 will be 11, and 5 will be 101. Thus, their \text{xor} will be 110 in binary, or 6 in decimal.

In short, 3 \text{ xor } 5 = 6, so the answer is 5.

Sample Input 2

10 12

Sample Output 2

6

Problem Statement

You are given two different strings S and T.
If S is lexicographically smaller than T, print Yes; otherwise, print No.

Note that many major programming languages implement lexicographical comparison of strings as operators or functions in standard libraries. For more detail, see your language's reference.

Constraints

• S and T are different strings, each of which consists of lowercase English letters and has a length of between 1 and 10 (inclusive).

Sample Input 1

abc atcoder

Sample Output 1

Yes

abc and atcoder begin with the same character, but their second characters are different. Since b comes earlier than t in alphabetical order, we can see that abc is lexicographically smaller than atcoder.

Sample Input 2

arc agc

Sample Output 2

No

Sample Input 3

a aa

Sample Output 3

Yes

Problem Statement

You are given N integers A_1, A_2, \ldots, A_N. Find the largest among those integers that are not the largest.

The constraints of this problem guarantee that the answer exists.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• It is not the case that all A_1, A_2, \ldots, A_N are equal.
• All input values are integers.

Sample Input 1

5
2 1 3 3 2

Sample Output 1

2

The largest integer among 2,1,3,3,2 is 3.

The integers that are not 3 among 2,1,3,3,2 are 2,1,2, among which the largest is 2.

Sample Input 2

4
4 3 2 1

Sample Output 2

3

Sample Input 3

8
22 22 18 16 22 18 18 22

Sample Output 3

18

Problem Statement

You are given a string S. Find the maximum length of a contiguous substring of S that is a palindrome.
Note that there is always a contiguous substring of S that is a palindrome.

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of uppercase English letters.

Sample Input 1

TOYOTA

Sample Output 1

5

TOYOT, a contiguous substring of TOYOTA, is a palindrome of length 5.
TOYOTA, the only length-6 contiguous substring of TOYOTA, is not a palindrome, so print 5.

Sample Input 2

ABCDEFG

Sample Output 2

1

Every contiguous substring of length 1 is a palindrome.

Sample Input 3

AAAAAAAAAA

Sample Output 3

10

Problem Statement

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

Determine whether there exists a non-empty (contiguous) subarray of A that has a repeated value, occurring multiple times in A. If such a subarray exists, find the length of the shortest such subarray.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^6 \ (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
3 9 5 3 1

Sample Output 1

4

(3,9,5,3) and (3,9,5,3,1) satisfy the condition. The shorter one is (3,9,5,3), which has length 4.

Sample Input 2

4
2 5 3 1

Sample Output 2

-1

There is no subarray that satisfies the condition.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55

Sample Output 3

2

Problem Statement

There are N sellers and M buyers in an apple market.

The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).

The i-th buyer may buy an apple for B_i yen or less.

Find the minimum integer X that satisfies the following condition.

Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.

Constraints

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

Sample Input 1

3 4
110 90 120
100 80 120 10000

Sample Output 1

110

Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.

Since an integer less than 110 does not satisfy the condition, this is the answer.

Sample Input 2

5 2
100000 100000 100000 100000 100000
100 200

Sample Output 2

201

Sample Input 3

3 2
100 100 100
80 120

Sample Output 3

100

Problem Statement

AtCoder cafeteria offers N main dishes and M side dishes. The price of the i-th main dish is A_i, and that of the j-th side dish is B_j. The cafeteria is considering introducing a new set meal menu. A set meal consists of one main dish and one side dish. Let s be the sum of the prices of the main dish and the side dish, then the price of the set meal is \min(s,P). Here, P is a constant given in the input.

There are NM ways to choose a main dish and a side dish for a set meal. Find the total price of all these set meals.

Constraints

• 1\leq N,M \leq 2\times 10^5
• 1\leq A_i,B_j \leq 10^8
• 1\leq P \leq 2\times 10^8
• All input values are integers.

Sample Input 1

2 2 7
3 5
6 1

Sample Output 1

24

• If you choose the first main dish and the first side dish, the price of the set meal is \min(3+6,7)=7.
• If you choose the first main dish and the second side dish, the price of the set meal is \min(3+1,7)=4.
• If you choose the second main dish and the first side dish, the price of the set meal is \min(5+6,7)=7.
• If you choose the second main dish and the second side dish, the price of the set meal is \min(5+1,7)=6.

Thus, the answer is 7+4+7+6=24.

Sample Input 2

1 3 2
1
1 1 1

Sample Output 2

6

Sample Input 3

7 12 25514963
2436426 24979445 61648772 23690081 33933447 76190629 62703497
11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857

Sample Output 3

2115597124

Problem Statement

You are given sequences of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
Let S be a subset of \lbrace1, 2, \dots, N\rbrace of size K. Here, find the minimum possible value of the following expression:

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 10^6
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
3 2
3 7 6
9 2 4
5 3
6 4 1 5 9
8 6 5 1 7
10 6
61 95 61 57 69 49 46 47 14 43
39 79 48 92 90 76 30 16 30 94

Sample Output 1

42
60
14579

In the first test case, for S = \{2, 3\}, the value of the expression is 7 \times (2 + 4) = 42, which is the minimum.

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

For each integer pair (L,R) with 1 \le L \le R \le N, define f(L,R) as follows:

• Start with an empty blackboard. Write the R-L+1 integers A_L, A_{L+1}, \ldots, A_R on the blackboard in order.
• Repeat the following operation until all integers on the blackboard are erased:
  • Choose integers l, r with l \le r such that every integer from l through r appears at least once on the blackboard. Then, erase all integers from l through r that are on the blackboard.
• Let f(L,R) be the minimum number of such operations needed to erase all the integers from the blackboard.

Find \displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R).

Constraints

• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le N
• All input values are integers.

Sample Input 1

4
1 3 1 4

Sample Output 1

16

For example, in the case of (L,R)=(1,4):

• The blackboard has 1,3,1,4.
• Choose (l,r)=(1,1) and erase all occurrences of 1. The blackboard now has 3,4.
• Choose (l,r)=(3,4) and erase all occurrences of 3 and 4. The blackboard becomes empty.
• It cannot be done in fewer than two operations, so f(1,4) = 2.

Similarly, you can find f(2,4)=2, f(1,1)=1, etc.

\displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R) = 16, so print 16.

Sample Input 2

5
3 1 4 2 4

Sample Output 2

23

Sample Input 3

10
5 1 10 9 2 5 6 9 1 6

Sample Output 3

129