Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a contiguous subarray B=(B_1,B_2,\dots,B_M) of A of length M.

Notes

A contiguous subarray of a number sequence is a sequence that is obtained by removing 0 or more initial terms and 0 or more final terms from the original number sequence.

For example, (2, 3) and (1, 2, 3) are contiguous subarrays of (1, 2, 3, 4), but (1, 3) and (3,2,1) are not contiguous subarrays of (1, 2, 3, 4).

Constraints

• 1 \le M \le N \le 2 \times 10^5
• - 2 \times 10^5 \le A_i \le 2 \times 10^5
• All values in input are integers.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

15

When B=(A_3,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15. Since it is impossible to achieve 16 or a larger value, the solution is 15.

Note that you are not allowed to choose, for instance, B=(A_1,A_4).

Sample Input 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

Sample Output 2

31

Problem Statement

Find the K-th lexicographically smallest string among the strings that are permutations of a string S.

Constraints

• 1 \le |S| \le 8
• S consists of lowercase English letters.
• There are at least K distinct strings that are permutations of S.

Sample Input 1

aab 2

Sample Output 1

aba

There are three permutations of a string aab: \{ aab, aba, baa \}. The 2-nd lexicographically smallest of them is aba.

Sample Input 2

baba 4

Sample Output 2

baab

Sample Input 3

ydxwacbz 40320

Sample Output 3

zyxwdcba

Problem Statement

There is an SNS used by N users, labeled with numbers from 1 to N.

In this SNS, two users can become friends with each other.
Friendship is bidirectional; if user X is a friend of user Y, user Y is always a friend of user X.

Currently, there are M pairs of friendships on the SNS, with the i-th pair consisting of users A_i and B_i.

Determine the maximum number of times the following operation can be performed:

• Operation: Choose three users X, Y, and Z such that X and Y are friends, Y and Z are friends, but X and Z are not. Make X and Z friends.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i < B_i \leq N
• The pairs (A_i, B_i) are distinct.
• All input values are integers.

Sample Input 1

4 3
1 2
2 3
1 4

Sample Output 1

3

Three new friendships with a friend's friend can occur as follows:

• User 1 becomes friends with user 3, who is a friend of their friend (user 2)
• User 3 becomes friends with user 4, who is a friend of their friend (user 1)
• User 2 becomes friends with user 4, who is a friend of their friend (user 1)

There will not be four or more new friendships.

Sample Input 2

3 0

Sample Output 2

0

If there are no initial friendships, no new friendships can occur.

Sample Input 3

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

Sample Output 3

12

Problem Statement

The Republic of AtCoder has N cities, called City 1, City 2, \ldots, City N. Initially, there was a bidirectional road between every pair of different cities, but M of these roads have become unusable due to deterioration over time. More specifically, for each 1\leq i \leq M, the road connecting City U_i and City V_i has become unusable.

Takahashi will go for a K-day trip that starts and ends in City 1. Formally speaking, a K-day trip that starts and ends in City 1 is a sequence of K+1 cities (A_0, A_1, \ldots, A_K) such that A_0=A_K=1 holds and for each 0\leq i\leq K-1, A_i and A_{i+1} are different and there is still a usable road connecting City A_i and City A_{i+1}.

Print the number of different K-day trips that start and end in City 1, modulo 998244353. Here, two K-day trips (A_0, A_1, \ldots, A_K) and (B_0, B_1, \ldots, B_K) are said to be different when there exists an i such that A_i\neq B_i.

Constraints

• 2 \leq N \leq 5000
• 0 \leq M \leq \min\left( \frac{N(N-1)}{2},5000 \right)
• 2 \leq K \leq 5000
• 1 \leq U_i<V_i \leq N
• All pairs (U_i, V_i) are pairwise distinct.
• All values in input are integers.

Sample Input 1

3 1 4
2 3

Sample Output 1

4

There are four different trips as follows.

• (1,2,1,2,1)
• (1,2,1,3,1)
• (1,3,1,2,1)
• (1,3,1,3,1)

No other trip is valid, so we should print 4.

Sample Input 2

3 3 3
1 2
1 3
2 3

Sample Output 2

0

No road remains usable, so there is no valid trip.

Sample Input 3

5 3 100
1 2
4 5
2 3

Sample Output 3

428417047

Problem Statement

Tiles are laid out on a coordinate plane. There are two types of tiles: small tiles of size 1\times1 and large tiles of size K\times K, laid out according to the following rules:

• For each pair of integers (i,j), the square \lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace is contained within either one small tile or one large tile.
  • If \left\lfloor\dfrac iK\right\rfloor+\left\lfloor\dfrac jK\right\rfloor is even, it is contained within a small tile.
  • Otherwise, it is contained within a large tile.

Tiles include their boundaries, and no two different tiles have a positive area of intersection.

For example, when K=3, tiles are laid out as follows:

Takahashi starts at the point (S_x+0.5,S_y+0.5) on the coordinate plane.

He can repeat the following movement any number of times:

• Choose a direction (up, down, left, or right) and a positive integer n. Move n units in that direction.

Each time he crosses from one tile to another, he must pay a toll of 1.

Determine the minimum toll Takahashi must pay to reach the point (T_x+0.5,T_y+0.5).

Constraints

• 1\leq K\leq10^{16}
• 0\leq S_x\leq2\times10^{16}
• 0\leq S_y\leq2\times10^{16}
• 0\leq T_x\leq2\times10^{16}
• 0\leq T_y\leq2\times10^{16}
• All input values are integers.

Sample Input 1

3
7 2
1 6

Sample Output 1

5

For example, he can move as follows, paying a toll of 5.

• Move up by 3. Pay a toll of 1.
• Move left by 2. Pay a toll of 1.
• Move up by 1. Pay a toll of 1.
• Move left by 4. Pay a toll of 2.

The toll paid cannot be 4 or less, so print 5.

Sample Input 2

1
41 42
13 56

Sample Output 2

42

When he moves the shortest distance, he will always pay a toll of 42.

The toll paid cannot be 41 or less, so print 42.

Sample Input 3

100
100 99
199 1

Sample Output 3

0

There are cases where no toll needs to be paid.

Sample Input 4

96929423
5105216413055191 10822465733465225
1543712011036057 14412421458305526

Sample Output 4

79154049