Problem Statement

Among the positive integers that consist of 0's and 2's when written in base 10, find the K-th smallest integer.

Constraints

• K is an integer between 1 and 10^{18} (inclusive).

Sample Input 1

3

Sample Output 1

22

The positive integers that consist of 0's and 2's when written in base 10 are 2,20,22,\dots in ascending order.
The (K=) 3-rd of them, which is 22, should be printed.

Sample Input 2

11

Sample Output 2

2022

Sample Input 3

923423423420220108

Sample Output 3

220022020000202020002022022000002020002222002200002022002200

Note that the exact value of the answer must be printed as an integer, even if it is big.

Problem Statement

You are given a string S of length N consisting of lowercase English letters, ,, and ". It is guaranteed that S contains an even number of ".

Let 2K be the number of " in S. For each i=1,2,\ldots,K, the characters from the (2i-1)-th " through the (2i)-th " are said to be enclosed.

Your task is to replace each , in S that is not an enclosed character with . and print the resulting string.

Constraints

• N is an integer between 1 and 2\times 10^5, inclusive.
• S is a string of length N consisting of lowercase English letters, ,, and ".
• S contains an even number of ".

Sample Input 1

8
"a,b"c,d

Sample Output 1

"a,b"c.d

In S, "a,b" are enclosed characters, and c,d are not.

The , in S that is not an enclosed character is the seventh character from the left in S, so replace that character with . to get the answer.

Sample Input 2

5
,,,,,

Sample Output 2

.....

Sample Input 3

20
a,"t,"c,"o,"d,"e,"r,

Sample Output 3

a."t,"c."o,"d."e,"r.

Problem Statement

You are given a string S of length N consisting of uppercase and lowercase English letters.

Let us perform Q operations on the string S. The i-th operation (1\leq i\leq Q) is represented by a tuple (t _ i,x _ i,c _ i) of two integers and one character, as follows.

• If t _ i=1, change the x _ i-th character of S to c _ i.
• If t _ i=2, convert all uppercase letters in S to lowercase (do not use x _ i,c _ i for this operation).
• If t _ i=3, convert all lowercase letters in S to uppercase (do not use x _ i,c _ i for this operation).

Print the S after the Q operations.

Constraints

• 1\leq N\leq5\times10^5
• S is a string of length N consisting of uppercase and lowercase English letters.
• 1\leq Q\leq5\times10^5
• 1\leq t _ i\leq3\ (1\leq i\leq Q)
• If t _ i=1, then 1\leq x _ i\leq N\ (1\leq i\leq Q).
• c _ i is an uppercase or lowercase English letter.
• If t _ i\neq 1, then x _ i=0 and c _ i= 'a'.
• N,Q,t _ i,x _ i are all integers.

Sample Input 1

7
AtCoder
5
1 4 i
3 0 a
1 5 b
2 0 a
1 4 Y

Sample Output 1

atcYber

Initially, the string S is AtCoder.

• The first operation changes the 4-th character to i, changing S to AtCider.
• The second operation converts all lowercase letters to uppercase, changing S to ATCIDER.
• The third operation changes the 5-th character to b, changing S to ATCIbER.
• The fourth operation converts all uppercase letters to lowercase, changing S to atciber.
• The fifth operation changes the 4-th character to Y, changing S to atcYber.

After the operations, the string S is atcYber, so print atcYber.

Sample Input 2

35
TheQuickBrownFoxJumpsOverTheLazyDog
10
2 0 a
1 19 G
1 13 m
1 2 E
1 21 F
2 0 a
1 27 b
3 0 a
3 0 a
1 15 i

Sample Output 2

TEEQUICKBROWMFiXJUGPFOVERTBELAZYDOG

Problem Statement

You are given integer sequences A = (a_1,\ldots,a_N) and B = (b_1,\ldots,b_N), each of length N.

For i=1,...,Q, answer the query in the following format.

• If the set of values contained in the first x_i terms of A, (a_1,\ldots,a_{x_i}), and the set of values contained in the first y_i terms of B, (b_1,\ldots,b_{y_i}), are equal, then print Yes; otherwise, print No.

Constraints

• 1 \leq N,Q \leq 2 \times 10^5
• 1 \leq a_i,b_i \leq 10^9
• 1 \leq x_i,y_i \leq N
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes
Yes
Yes
No
No
Yes
No

Note that sets are a concept where it matters only whether each value is contained or not.
For the 3-rd query, the first 2 terms of A contain one 1 and one 2, while the first 3 terms of B contain one 1 and two 2's. However, the sets of values contained in the segments are both \{ 1,2 \}, which are equal.
Also, for the 6-th query, the values appear in different orders, but they are still equal as sets.

Problem Statement

In an N-dimensional space, the Manhattan distance d(x,y) between two points x=(x_1, x_2, \dots, x_N) and y = (y_1, y_2, \dots, y_N) is defined by:

A point x=(x_1, x_2, \dots, x_N) is said to be a lattice point if the components x_1, x_2, \dots, x_N are all integers.

You are given lattice points p=(p_1, p_2, \dots, p_N) and q = (q_1, q_2, \dots, q_N) in an N-dimensional space.
How many lattice points r satisfy d(p,r) \leq D and d(q,r) \leq D? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 100
• 0 \leq D \leq 1000
• -1000 \leq p_i, q_i \leq 1000
• All values in input are integers.

Sample Input 1

1 5
0
3

Sample Output 1

8

When N=1, we consider points in a one-dimensional space, that is, on a number line.
8 lattice points satisfy the conditions: -2,-1,0,1,2,3,4,5.

Sample Input 2

3 10
2 6 5
2 1 2

Sample Output 2

632

Sample Input 3

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

Sample Output 3

145428186