Problem Statement

You are given an integer N.
Print an approximation of N according to the following instructions.

• If N is less than or equal to 10^3-1, print N as it is.
• If N is between 10^3 and 10^4-1, inclusive, truncate the ones digit of N and print the result.
• If N is between 10^4 and 10^5-1, inclusive, truncate the tens digit and all digits below it of N and print the result.
• If N is between 10^5 and 10^6-1, inclusive, truncate the hundreds digit and all digits below it of N and print the result.
• If N is between 10^6 and 10^7-1, inclusive, truncate the thousands digit and all digits below it of N and print the result.
• If N is between 10^7 and 10^8-1, inclusive, truncate the ten-thousands digit and all digits below it of N and print the result.
• If N is between 10^8 and 10^9-1, inclusive, truncate the hundred-thousands digit and all digits below it of N and print the result.

Constraints

• N is an integer between 0 and 10^9-1, inclusive.

Sample Input 1

20230603

Sample Output 1

20200000

20230603 is between 10^7 and 10^8-1 (inclusive).
Therefore, truncate the ten-thousands digit and all digits below it, and print 20200000.

Sample Input 2

0

Sample Output 2

0

Sample Input 3

304

Sample Output 3

304

Sample Input 4

500600

Sample Output 4

500000

Problem Statement

You are given two strings S and T consisting of lowercase English letters. The lengths of S and T are N and M, respectively. (The constraints guarantee that N \leq M.)

S is said to be a prefix of T when the first N characters of T coincide S.
S is said to be a suffix of T when the last N characters of T coincide S.

If S is both a prefix and a suffix of T, print 0;
If S is a prefix of T but not a suffix, print 1;
If S is a suffix of T but not a prefix, print 2;
If S is neither a prefix nor a suffix of T, print 3.

Constraints

• 1 \leq N \leq M \leq 100
• S is a string of length N consisting of lowercase English letters.
• T is a string of length M consisting of lowercase English letters.

Sample Input 1

3 7
abc
abcdefg

Sample Output 1

1

S is a prefix of T but not a suffix, so you should print 1.

Sample Input 2

3 4
abc
aabc

Sample Output 2

2

S is a suffix of T but not a prefix.

Sample Input 3

3 3
abc
xyz

Sample Output 3

3

S is neither a prefix nor a suffix of T.

Sample Input 4

3 3
aaa
aaa

Sample Output 4

0

S and T may coincide, in which case S is both a prefix and a suffix of T.

Problem Statement

Takahashi runs an SNS "Twidai," which has N users from user 1 through user N. In Twidai, users can follow or unfollow other users.

Q operations have been performed since Twidai was launched. The i-th (1\leq i\leq Q) operation is represented by three integers T_i, A_i, and B_i, whose meanings are as follows:

• If T_i = 1: it means that user A_i follows user B_i. If user A_i is already following user B_i at the time of this operation, it does not make any change.
• If T_i = 2: it means that user A_i unfollows user B_i. If user A_i is not following user B_i at the time of this operation, it does not make any change.
• If T_i = 3: it means that you are asked to determine if users A_i and B_i are following each other. You need to print Yes if user A_i is following user B_i and user B_i is following user A_i, and No otherwise.

When the service was launched, no users were following any users.

Print the correct answers for all operations such that T_i = 3 in ascending order of i.

Constraints

• 2 \leq N \leq 10 ^ 9
• 1 \leq Q \leq 2\times10 ^ 5
• T _ i=1,2,3\ (1\leq i\leq Q)
• 1 \leq A _ i \leq N\ (1\leq i\leq Q)
• 1 \leq B _ i \leq N\ (1\leq i\leq Q)
• A _ i\neq B _ i\ (1\leq i\leq Q)
• There exists i\ (1\leq i\leq Q) such that T _ i=3.
• All values in the input are integers.

Sample Input 1

3 9
1 1 2
3 1 2
1 2 1
3 1 2
1 2 3
1 3 2
3 1 3
2 1 2
3 1 2

Sample Output 1

No
Yes
No
No

Twidai has three users. The nine operations are as follows.

• User 1 follows user 2. No other users are following or followed by any users.
• Determine if users 1 and 2 are following each other. User 1 is following user 2, but user 2 is not following user 1, so No is the correct answer to this operation.
• User 2 follows user 1.
• Determine if users 1 and 2 are following each other. User 1 is following user 2, and user 2 is following user 1, so Yes is the correct answer to this operation.
• User 2 follows user 3.
• User 3 follows user 2.
• Determine if users 1 and 3 are following each other. User 1 is not following user 3, and user 3 is not following user 1, so No is the correct answer to this operation.
• User 1 unfollows user 2.
• Determine if users 1 and 2 are following each other. User 2 is following user 1, but user 1 is not following user 2, so No is the correct answer to this operation.

Sample Input 2

2 8
1 1 2
1 2 1
3 1 2
1 1 2
1 1 2
1 1 2
2 1 2
3 1 2

Sample Output 2

Yes
No

A user may follow the same user multiple times.

Sample Input 3

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

Sample Output 3

No
No
No
No
Yes
Yes
No
No
No
Yes
Yes

Problem Statement

A region has N towns numbered 1 to N, and M roads numbered 1 to M.

The i-th road connects town A_i and town B_i bidirectionally with length C_i.

Find the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once.

Constraints

• 2 \leq N \leq 10
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• The pairs (A_i,B_i) are distinct.
• 1\leq C_i \leq 10^8
• All input values are integers.

Sample Input 1

4 4
1 2 1
2 3 10
1 3 100
1 4 1000

Sample Output 1

1110

If you travel as 4\to 1\to 3\to 2, the total length of the roads you traverse is 1110.

Sample Input 2

10 1
5 9 1

Sample Output 2

1

There may be a town that is not connected to a road.

Sample Input 3

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

Sample Output 3

20

Problem Statement

You are given a sequence of positive integers A=(a_1,\ldots,a_N) of length N.
There are (2^N-1) ways to choose one or more terms of A. How many of them have an integer-valued average? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 100
• 1 \leq a_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
2 6 2

Sample Output 1

6

For each way to choose terms of A, the average is obtained as follows:

• If just a_1 is chosen, the average is \frac{a_1}{1}=\frac{2}{1} = 2, which is an integer.

• If just a_2 is chosen, the average is \frac{a_2}{1}=\frac{6}{1} = 6, which is an integer.

• If just a_3 is chosen, the average is \frac{a_3}{1}=\frac{2}{1} = 2, which is an integer.

• If a_1 and a_2 are chosen, the average is \frac{a_1+a_2}{2}=\frac{2+6}{2} = 4, which is an integer.

• If a_1 and a_3 are chosen, the average is \frac{a_1+a_3}{2}=\frac{2+2}{2} = 2, which is an integer.

• If a_2 and a_3 are chosen, the average is \frac{a_2+a_3}{2}=\frac{6+2}{2} = 4, which is an integer.

• If a_1, a_2, and a_3 are chosen, the average is \frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3}, which is not an integer.

Therefore, 6 ways satisfy the condition.

Sample Input 2

5
5 5 5 5 5

Sample Output 2

31

Regardless of the choice of one or more terms of A, the average equals 5.