Problem Statement

Takahashi monitored a factory machine for N days and recorded the load level each day as a single digit from 0 to 9. The record is represented by a string S of length N, where the i-th character of S is the load level on day i.

Find the highest load level observed over the N days.

Constraints

• 1 \leq N \leq 100
• S is a string of length N consisting only of digits from 0 to 9.

Sample Input 1

4
3715

Sample Output 1

7

Sample Input 2

2
44

Sample Output 2

4

Sample Input 3

4
4321

Sample Output 3

4

Sample Input 4

46
5001109154852658893042839798352710745703959824

Sample Output 4

9

Sample Input 5

6
562042

Sample Output 5

6

Problem Statement

Takahashi has come to an udon restaurant. The seats in the restaurant are arranged in H rows and W columns, and the seating chart is represented by H strings S_1, S_2, \ldots, S_H. The j-th character of S_i describes the seat in the i-th row from the top and the j-th column from the left: o means a person is sitting there, and . means the seat is empty.

Takahashi wants to sit in the row with the most empty seats. Find which row from the top has the most empty seats. If there are multiple such rows, answer the topmost one among them.

Constraints

• 1 \leq H \leq 10
• 1 \leq W \leq 10
• S_i is a string of length W consisting only of o and ..

Sample Input 1

3 4
oo.o
..o.
ooo.

Sample Output 1

2

Sample Input 2

1 3
ooo

Sample Output 2

1

Sample Input 3

2 2
..
o.

Sample Output 3

1

Sample Input 4

3 2
.o
o.
..

Sample Output 4

3

Sample Input 5

4 4
oooo
o.oo
.o.o
.o..

Sample Output 5

4

Problem Statement

Takahashi is planning an N-day trip. The cost for the i-th day (1 \le i \le N) of the trip is A_i yen.

To adjust his budget, Takahashi has decided to cancel a contiguous range of days from the trip's schedule. Specifically, he will choose one of the following 1 + \frac{N(N+1)}{2} options:

• Do not cancel any days. In this case, the total cost will be \sum_{i=1}^N A_i yen.
• Choose a pair of integers (l, r) satisfying 1 \le l \le r \le N, and cancel the schedule from day l through day r. In this case, the total cost will be \sum_{i=1}^N A_i - \sum_{i=l}^r A_i yen.

Find the number of options among the above such that the total cost for the days the trip takes place is exactly K yen.

Constraints

• 1 \le N \le 10^6
• 0 \le K \le 10^{15}
• 1 \le A_i \le 10^9 (1 \le i \le N)
• All input values are integers.

Sample Input 1

4 5
2 3 1 4

Sample Output 1

2

Sample Input 2

3 8
1 2 3

Sample Output 2

0

Sample Input 3

10 6
2 1 3 1 2 1 3 2 1 2

Sample Output 3

2

Sample Input 4

15 2500000000
500000000 300000000 200000000 800000000 200000000 400000000 600000000 1000000000 100000000 900000000 700000000 300000000 500000000 400000000 600000000

Sample Output 4

2

Sample Input 5

1 0
100

Sample Output 5

1

Problem Statement

Takahashi is operating an autonomous robot on a test course consisting of a grid with H rows and W columns.

Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

The state of each cell (i, j) is represented by an integer A_{i, j}. If A_{i, j} = 0, cell (i, j) is an empty cell and can be entered. If A_{i, j} = 1, cell (i, j) contains an obstacle and cannot be entered.

It is guaranteed that cells (1, 1) and (H, W) are empty cells.

The robot is initially placed at cell (1, 1). It aims to reach cell (H, W) by repeatedly moving 1 cell to an adjacent passable cell in the up, down, left, or right direction within the grid. It is allowed to visit the same cell multiple times during the movement.

However, due to mechanical constraints, the robot must alternate between moving vertically (up or down) and moving horizontally (left or right).

More precisely, the moves must satisfy the following conditions:

• In the first move, the robot may move in either the vertical or horizontal direction.
• If the previous move was in the vertical direction, the next move must be in the horizontal direction.
• If the previous move was in the horizontal direction, the next move must be in the vertical direction.

Determine whether the robot can reach cell (H, W) from cell (1, 1), and if it is possible, find the minimum number of moves required.

Constraints

• 2 \leq H \leq 1000
• 2 \leq W \leq 1000
• A_{i, j} \in \{0, 1\} (1 \leq i \leq H,\ 1 \leq j \leq W)
• A_{1, 1} = 0
• A_{H, W} = 0
• All input values are integers.

Sample Input 1

3 3
0 1 0
0 0 0
0 0 0

Sample Output 1

4

Sample Input 2

3 3
0 0 0
0 1 0
0 0 0

Sample Output 2

NONE

Sample Input 3

5 5
0 0 1 1 1
1 0 0 1 1
1 0 0 1 1
1 0 0 0 0
1 1 0 0 0

Sample Output 3

12

Sample Input 4

8 8
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 0 0
1 1 1 1 1 1 0 0
1 1 1 1 1 1 0 0
1 1 1 1 1 1 0 0
1 1 1 1 1 1 0 0
1 1 1 1 1 1 0 0

Sample Output 4

22

Sample Input 5

2 2
0 0
0 0

Sample Output 5

2

Problem Statement

Takahashi is a mountain guide responsible for managing a mountain trail. There are N checkpoints arranged in a line along the trail, numbered 1, 2, \ldots, N from left to right. The elevation of each checkpoint i is A_i. Because steep changes in elevation significantly drain climbers' stamina, Takahashi wants to manage climbers' fatigue levels.

During the trail's management, a total of Q events of the following two types occur:

• Event 1: Due to changes in terrain, the elevation of checkpoint p is changed to v.
• Event 2: Aoki comes hiking and tells Takahashi that he plans to walk from checkpoint l to checkpoint r. Takahashi must compute and report the fatigue level that Aoki will experience on this segment.

The method for calculating the fatigue level in Event 2 is defined precisely below.

Let S = \{(i, i+1) \mid l \le i \le r-1\} be the set of adjacent pairs contained in the interval [l, r], and let d_i = |A_i - A_{i+1}| be the absolute difference in elevation for each adjacent pair (i, i+1).

1. If S is empty (i.e., l = r), the fatigue level is 0.
2. If S is non-empty, let M_1 = \max_{(i,i+1) \in S} d_i.

• If M_1 \le K, the fatigue level is M_1.
• If M_1 > K, Aoki can use a detour to bypass (shortcut) exactly one adjacent pair from S. Aoki chooses which adjacent pair to bypass optimally to minimize the fatigue level. That is, the fatigue level is \min_{(j, j+1) \in S} \left( \max_{(i,i+1) \in S \setminus \{(j,j+1)\}} d_i \right). However, if the size of S is 1 (i.e., r = l+1), no adjacent pairs remain after the bypass, so the fatigue level is 0.

For each Event 2, find the fatigue level determined as described above.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq K \leq 10^9
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
• In Event 1, 1 \leq p \leq N and 0 \leq v \leq 10^9.
• In Event 2, 1 \leq l \leq r \leq N.
• All input values are integers.

Sample Input 1

5 8 5
10 13 20 18 25
2 1 5
2 2 4
2 3 3
1 3 15
2 1 5
1 5 16
2 4 5
2 1 2

Sample Output 1

7
2
0
3
2
3

Sample Input 2

4 7 10
0 4 9 15
2 1 4
2 1 1
1 2 20
2 1 3
1 4 5
2 2 4
2 3 4

Sample Output 2

6
0
11
4
4

Sample Input 3

10 15 7
5 12 3 8 20 21 10 30 25 27
2 1 10
2 3 6
1 5 9
2 1 6
2 5 5
1 7 35
2 6 8
1 1 100
2 1 3
2 4 10
1 10 0
2 8 10
1 2 100
2 1 2
2 1 10

Sample Output 3

12
5
9
0
5
9
12
5
0
25

Sample Input 4

20 25 50
100 180 160 300 290 400 405 1000 950 970 30 35 500 490 495 800 100 120 130 700
2 1 20
2 1 2
2 10 15
1 8 930
2 7 10
1 11 900
2 9 12
2 12 12
1 1 0
2 1 5
1 20 1000
2 16 20
1 17 850
2 15 18
1 5 100
2 3 6
2 6 14
1 13 910
2 11 14
1 2 0
2 1 3
2 18 20
1 10 200
2 8 11
2 1 20

Sample Output 4

700
0
465
20
70
0
140
700
305
200
525
865
0
10
700
870

Sample Input 5

2 10 0
0 1000000000
2 1 1
2 1 2
1 2 0
2 1 2
1 1 1000000000
2 1 2
1 2 1000000000
2 1 2
1 1 0
2 1 2

Sample Output 5

0
0
0
0
0
0