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

There is a two-dimensional plane. For integers r and c between 1 and 9, there is a pawn at the coordinates (r,c) if the c-th character of S_{r} is #, and nothing if the c-th character of S_{r} is ..

Find the number of squares in this plane with pawns placed at all four vertices.

Constraints

• Each of S_1,\ldots,S_9 is a string of length 9 consisting of # and ..

Sample Input 1

##.......
##.......
.........
.......#.
.....#...
........#
......#..
.........
.........

Sample Output 1

2

The square with vertices (1,1), (1,2), (2,2), and (2,1) have pawns placed at all four vertices.

The square with vertices (4,8), (5,6), (7,7), and (6,9) also have pawns placed at all four vertices.

Thus, the answer is 2.

Sample Input 2

.#.......
#.#......
.#.......
.........
....#.#.#
.........
....#.#.#
........#
.........

Sample Output 2

3

Problem Statement

You are given a simple undirected graph G with N vertices and M edges (a simple graph does not contain self-loops or multi-edges). For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i.

Print the number of pairs of integers (u, v) that satisfy 1 \leq u \lt v \leq N and both of the following conditions.

• The graph G does not have an edge connecting vertex u and vertex v.
• Adding an edge connecting vertex u and vertex v in the graph G results in a bipartite graph.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min \lbrace 2 \times 10^5, N(N-1)/2 \rbrace
• 1 \leq u_i, v_i \leq N
• The graph G is simple.
• All values in the input are integers.

Sample Input 1

5 4
4 2
3 1
5 2
3 2

Sample Output 1

2

We have two pairs of integers (u, v) that satisfy the conditions in the problem statement: (1, 4) and (1, 5). Thus, you should print 2.
The other pairs do not satisfy the conditions. For instance, for (1, 3), the graph G has an edge connecting vertex 1 and vertex 3; for (4, 5), adding an edge connecting vertex 4 and vertex 5 in the graph G does not result in a bipartite graph.

Sample Input 2

4 3
3 1
3 2
1 2

Sample Output 2

0

Note that the given graph may not be bipartite or connected.

Sample Input 3

9 11
4 9
9 1
8 2
8 3
9 2
8 4
6 7
4 6
7 5
4 5
7 8

Sample Output 3

9

Problem Statement

Takahashi and Aoki walk on a two-dimensional plane.

Takahashi's start point is (TS_X, TS_Y) and goal point is (TG_X, TG_Y). Aoki's start point is (AS_X, AS_Y) and goal point is (AG_X, AG_Y).

They simultaneously depart from their respective start points and walk straight toward their respective goal points at speed 1, and stop when they reach their respective goal points. (Note that they depart simultaneously, but they do not necessarily stop at the same time.)

Find the distance between them at the moment when the distance between them is shortest (including the moment they depart and after they stop).

Here, distance refers to Euclidean distance. That is, the distance between two points (x_1,y_1),(x_2,y_2) is defined as \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}.

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

Constraints

• 1\leq T\leq 2\times 10^5
• -100\leq TS_X,TS_Y,TG_X,TG_Y,AS_X,AS_Y,AG_X,AG_Y \leq 100
• (TS_X,TS_Y)\neq (TG_X,TG_Y)
• (AS_X,AS_Y)\neq (AG_X,AG_Y)
• All input values are integers.

Sample Input 1

4
0 0 -2 2
-1 -1 4 4
4 0 2 0
6 0 8 0
1 0 1 1
-1 0 1 1
-8 9 2 6
-10 -10 17 20

Sample Output 1

1.000000000000000
2.000000000000000
0.000000000000000
1.783905950993199

For the first test case, let time 0 be the moment they depart. Their behavior is as follows:

• Time 0: Takahashi departs from (0,0) and starts walking toward (-2,2) at speed 1. At the same time, Aoki departs from (-1,-1) and starts walking toward (4,4) at speed 1.
• Time 2\sqrt{2}: Takahashi reaches his goal point (-2,2) and stops. At this time, Aoki is at (1,1) and is still walking.
• Time 5\sqrt{2}: Aoki reaches his goal point (4,4) and stops.

The distance between them is shortest at time \frac{1}{\sqrt{2}}, when Takahashi and Aoki are at (-\frac{1}{2},\frac{1}{2}) and (-\frac{1}{2},-\frac{1}{2}) respectively, and the distance is 1.

For the second test case, the distance between them is shortest at the moment they depart, and the distance at that time is 2.

For the third test case, the distance between them is shortest after they both stop, and the distance at that time is 0.

Problem Statement

We have N dice. For each i = 1, 2, \ldots, N, when the i-th die is thrown, it shows a random integer between 1 and A_i, inclusive, with equal probability.

Find the probability, modulo 998244353, that the following condition is satisfied when the N dice are thrown simultaneously.

There is a way to choose some (possibly all) of the N dice so that the sum of their results is 10.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 10^6
• All input values are integers.

Sample Input 1

4
1 7 2 9

Sample Output 1

942786334

For instance, if the first, second, third, and fourth dice show 1, 3, 2, and 7, respectively, these results satisfy the condition. In fact, if the second and fourth dice are chosen, the sum of their results is 3 + 7 = 10. Alternatively, if the first, third, and fourth dice are chosen, the sum of their results is 1 + 2 + 7 = 10.

On the other hand, if the first, second, third, and fourth dice show 1, 6, 1, and 5, respectively, there is no way to choose some of them so that the sum of their results is 10, so the condition is not satisfied.

In this sample input, the probability of the results of the N dice satisfying the condition is \frac{11}{18}. Thus, print this value modulo 998244353, that is, 942786334.

Sample Input 2

7
1 10 100 1000 10000 100000 1000000

Sample Output 2

996117877