Problem Statement

Takahashi is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

• Takahashi's coordinates after the i-th move are:

  • (x+1,y) if the i-th character of S is R;
  • (x-1,y) if the i-th character of S is L;
  • (x,y+1) if the i-th character of S is U; and
  • (x,y-1) if the i-th character of S is D,

  where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

• 1 \leq N \leq 2\times 10^5
• N is an integer.
• S is a string of length N consisting of R, L, U, and D.

Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).

Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No

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

There are N squares indexed 0 through (N-1) arranged in a line. Snuke is going to mark every square by the following procedure.

1. Mark square 0.
2. Repeat the following steps i - iii (N-1) times.
   1. Initialize a variable x with (A+D) \bmod N, where A is the index of the square marked last time.
   2. While square x is marked, repeat replacing x with (x+1) \bmod N.
   3. Mark square x.

Find the index of the square that Snuke marks for the K-th time.

Given T test cases, find the answer for each of them.

Constraints

• 1\leq T \leq 10^5
• 1\leq K\leq N \leq 10^9
• 1\leq D \leq 10^9
• All values in the input are integers.

Sample Input 1

9
4 2 1
4 2 2
4 2 3
4 2 4
5 8 1
5 8 2
5 8 3
5 8 4
5 8 5

Sample Output 1

0
2
1
3
0
3
1
4
2

If N=4 and D=2, Snuke marks the squares as follows.

1. Mark square 0.
2. (1-st iteration) Let x=(0+2)\bmod 4=2. Since square 2 is not marked, mark it.
   (2-nd iteration) Let x=(2+2)\bmod 4=0. Since square 0 is marked, let x=(0+1)\bmod 4=1. Since square 1 is not marked, mark it.
   (3-rd iteration) Let x=(1+2)\bmod 4=3. Since square 3 is not marked, mark it.

Problem Statement

You are given a sequence A=(A_0,A_1,\ldots,A_{N-1}) of length N.
There is an initially empty dish. Takahashi is going to repeat the following operation K times.

• Let X be the number of candies on the dish. He puts A_{(X\bmod N)} more candies on the dish. Here, X\bmod N denotes the remainder when X is divided by N.

Find how many candies are on the dish after the K operations.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq K \leq 10^{12}
• 1 \leq A_i\leq 10^6
• All values in input are integers.

Sample Input 1

5 3
2 1 6 3 1

Sample Output 1

11

The number of candies on the dish transitions as follows.

• In the 1-st operation, we have X=0, so A_{(0\mod 5)}=A_0=2 more candies will be put on the dish.
• In the 2-nd operation, we have X=2, so A_{(2\mod 5)}=A_2=6 more candies will be put on the dish.
• In the 3-rd operation, we have X=8, so A_{(8\mod 5)}=A_3=3 more candies will be put on the dish.

Thus, after the 3 operations, there will be 11 candies on the dish. Note that you must not print the remainder divided by N.

Sample Input 2

10 1000000000000
260522 914575 436426 979445 648772 690081 933447 190629 703497 47202

Sample Output 2

826617499998784056

The answer may not fit into a 32-bit integer type.

Problem Statement

You are given a sequence of non-negative integers A=(a_1,\ldots,a_N).

Let us perform the following operation on A just once.

• Choose a non-negative integer x. Then, for every i=1, \ldots, N, replace the value of a_i with the bitwise XOR of a_i and x.

Let M be the maximum value in A after the operation. Find the minimum possible value of M.

Constraints

• 1 \leq N \leq 1.5 \times 10^5
• 0 \leq a_i \lt 2^{30}
• All values in the input are integers.

Sample Input 1

3
12 18 11

Sample Output 1

16

If we do the operation with x=2, the sequence becomes (12 \oplus 2,18 \oplus 2, 11 \oplus 2) = (14,16,9), where the maximum value M is 16.
We cannot make M smaller than 16, so this value is the answer.

Sample Input 2

10
0 0 0 0 0 0 0 0 0 0

Sample Output 2

0

Sample Input 3

5
324097321 555675086 304655177 991244276 9980291

Sample Output 3

805306368