Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1,2,\dots,N and the edges are numbered 1,2,\dots,M. Edge i connects vertices A_i and B_i.

Determine whether this graph is a cycle graph.

Constraints

• 3 \le N \le 2\times 10^5
• 0 \le M \le 2\times 10^5
• 1 \le A_i, B_i \le N
• The given graph is simple.
• All input values are integers.

Sample Input 1

4 4
2 4
3 1
4 1
2 3

Sample Output 1

Yes

The given graph is as follows, and this is a cycle graph.

Sample Input 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

No

The given graph is as follows, and this is not a cycle graph.

Problem Statement

The decimal representation of 414 is 414, which is a palindrome. Also, the octal representation of 414 is 636, which is also a palindrome. Based on this, solve the following problem.

You are given positive integers A and N. Find the sum of all integers between 1 and N, inclusive, whose decimal representation and base-A representation are both palindromes.

Under the constraints of this problem, it can be proved that the answer is less than 2^{63}.

Constraints

• 2 \leq A \leq 9
• 1 \leq N \le 10^{12}
• All input values are integers.

Sample Input 1

8
1000

Sample Output 1

2155

The integers satisfying the condition are 1,2,3,4,5,6,7,9,121,292,333,373,414,585 (14 integers), and their sum is 2155.

Sample Input 2

8
999999999999

Sample Output 2

914703021014

Sample Input 3

6
999999999999

Sample Output 3

283958331810

Problem Statement

You are given a string S=S_1S_2\dots S_N of length N consisting of lowercase English letters. You will perform the following operation on S exactly once:

• Choose a contiguous substring of S with length at least 1 and cyclically shift it to the left by 1. That is, choose integers 1 \leq \ell \leq r \leq N, insert S_\ell to the right of the r-th character of S, and then delete the \ell-th character of S.

Find the lexicographically smallest string among all possible strings that S can become after the operation.

You are given T test cases, so solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^5
• S is a string of length N consisting of lowercase English letters.
• T and N are integers.
• The sum of N over all test cases in a single input file is at most 10^5.

Sample Input 1

3
7
atcoder
1
x
5
snuke

Sample Output 1

acodert
x
nsuke

• In the first test case, cyclically shifting from the 2nd to the 7th character gives acodert, which is lexicographically smallest.
• In the second test case, no matter how you operate, you get x.
• In the third test case, cyclically shifting from the 1st to the 2nd character gives nsuke, which is lexicographically smallest.

Problem Statement

There are N rectangular cuboids in a three-dimensional space.

These cuboids do not overlap. Formally, for any two different cuboids among them, their intersection has a volume of 0.

The diagonal of the i-th cuboid is a segment that connects two points (X_{i,1},Y_{i,1},Z_{i,1}) and (X_{i,2},Y_{i,2},Z_{i,2}), and its edges are all parallel to one of the coordinate axes.

For each cuboid, find the number of other cuboids that share a face with it.
Formally, for each i, find the number of j with 1\leq j \leq N and j\neq i such that the intersection of the surfaces of the i-th and j-th cuboids has a positive area.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq X_{i,1} < X_{i,2} \leq 100
• 0 \leq Y_{i,1} < Y_{i,2} \leq 100
• 0 \leq Z_{i,1} < Z_{i,2} \leq 100
• Cuboids do not have an intersection with a positive volume.
• All input values are integers.

Sample Input 1

4
0 0 0 1 1 1
0 0 1 1 1 2
1 1 1 2 2 2
3 3 3 4 4 4

Sample Output 1

1
1
0
0

The 1-st and 2-nd cuboids share a rectangle whose diagonal is the segment connecting two points (0,0,1) and (1,1,1).
The 1-st and 3-rd cuboids share a point (1,1,1), but do not share a surface.

Sample Input 2

3
0 0 10 10 10 20
3 4 1 15 6 10
0 9 6 1 20 10

Sample Output 2

2
1
1

Sample Input 3

8
0 0 0 1 1 1
0 0 1 1 1 2
0 1 0 1 2 1
0 1 1 1 2 2
1 0 0 2 1 1
1 0 1 2 1 2
1 1 0 2 2 1
1 1 1 2 2 2

Sample Output 3

3
3
3
3
3
3
3
3

Problem Statement

You are given a string S of length N consisting of 0 and 1. Let S_i denote the i-th character of S.

Process Q queries in the order they are given.
Each query is represented by a tuple of three integers (c, L, R), where c represents the type of the query.

• When c=1: For each integer i such that L \leq i \leq R, if S_i is 1, change it to 0; if it is 0, change it to 1.
• When c=2: Let T be the string obtained by extracting the L-th through R-th characters of S. Print the maximum number of consecutive 1s in T.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq Q \leq 10^5
• S is a string of length N consisting of 0 and 1.
• c \in \lbrace 1, 2 \rbrace
• 1 \leq L \leq R \leq N
• N, Q, c, L, and R are all integers.

Sample Input 1

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

Sample Output 1

3
1
0
7

The queries are processed as follows.

• Initially, S= 1101110.
• For the first query, T = 1101110. The longest sequence of consecutive 1s in T is 111 from the 4-th character to 6-th character, so the answer is 3.
• For the second query, T = 101. The longest sequence of consecutive 1s in T is 1 at the 1-st or 3-rd character, so the answer is 1.
• For the third query, the operation changes S to 1110000.
• For the fourth query, T = 00. T does not contain 1, so the answer is 0.
• For the fifth query, the operation changes S to 1111111.
• For the sixth query, T = 1111111. The longest sequence of consecutive 1s in T is 1111111 from the 1-st to 7-th characters, so the answer is 7.