Problem Statement

There are N people standing in a row from west to east. Each person is facing east or west. The directions of the people is given as a string S of length N. The i-th person from the west is facing east if S_i = E, and west if S_i = W.

You will appoint one of the N people as the leader, then command the rest of them to face in the direction of the leader. Here, we do not care which direction the leader is facing.

The people in the row hate to change their directions, so you would like to select the leader so that the number of people who have to change their directions is minimized. Find the minimum number of people who have to change their directions.

Constraints

• 2 \leq N \leq 3 \times 10^5
• |S| = N
• S_i is E or W.

Sample Input 1

5
WEEWW

Sample Output 1

1

Assume that we appoint the third person from the west as the leader. Then, the first person from the west needs to face east and has to turn around. The other people do not need to change their directions, so the number of people who have to change their directions is 1 in this case. It is not possible to have 0 people who have to change their directions, so the answer is 1.

Sample Input 2

12
WEWEWEEEWWWE

Sample Output 2

4

Sample Input 3

8
WWWWWEEE

Sample Output 3

3

Problem Statement

There is an integer sequence A of length N.

Find the number of the pairs of integers l and r (1 \leq l \leq r \leq N) that satisfy the following condition:

• A_l\ xor\ A_{l+1}\ xor\ ...\ xor\ A_r = A_l\ +\ A_{l+1}\ +\ ...\ +\ A_r

Here, xor denotes the bitwise exclusive OR.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i < 2^{20}
• All values in input are integers.

Sample Input 1

4
2 5 4 6

Sample Output 1

5

(l,r)=(1,1),(2,2),(3,3),(4,4) clearly satisfy the condition. (l,r)=(1,2) also satisfies the condition, since A_1\ xor\ A_2 = A_1\ +\ A_2 = 7. There are no other pairs that satisfy the condition, so the answer is 5.

Sample Input 2

9
0 0 0 0 0 0 0 0 0

Sample Output 2

45

Sample Input 3

19
885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1

Sample Output 3

37

Problem Statement

You are given an integer sequence A of length N and an integer K. You will perform the following operation on this sequence Q times:

• Choose a contiguous subsequence of length K, then remove the smallest element among the K elements contained in the chosen subsequence (if there are multiple such elements, choose one of them as you like).

Let X and Y be the values of the largest and smallest element removed in the Q operations. You would like X-Y to be as small as possible. Find the smallest possible value of X-Y when the Q operations are performed optimally.

Constraints

• 1 \leq N \leq 2000
• 1 \leq K \leq N
• 1 \leq Q \leq N-K+1
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

5 3 2
4 3 1 5 2

Sample Output 1

1

In the first operation, whichever contiguous subsequence of length 3 we choose, the minimum element in it is 1. Thus, the first operation removes A_3=1 and now we have A=(4,3,5,2). In the second operation, it is optimal to choose (A_2,A_3,A_4)=(3,5,2) as the contiguous subsequence of length 3 and remove A_4=2. In this case, the largest element removed is 2, and the smallest is 1, so their difference is 2-1=1.

Sample Input 2

10 1 6
1 1 2 3 5 8 13 21 34 55

Sample Output 2

7

Sample Input 3

11 7 5
24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784

Sample Output 3

451211184

Problem Statement

There is a simple undirected graph with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects Vertex U_i and V_i. Also, Vertex i has two predetermined integers A_i and B_i. You will play the following game on this graph.

First, choose one vertex and stand on it, with W yen (the currency of Japan) in your pocket. Here, A_s \leq W must hold, where s is the vertex you choose. Then, perform the following two kinds of operations any number of times in any order:

• Choose one vertex v that is directly connected by an edge to the vertex you are standing on, and move to vertex v. Here, you need to have at least A_v yen in your pocket when you perform this move.
• Donate B_v yen to the vertex v you are standing on. Here, the amount of money in your pocket must not become less than 0 yen.

You win the game when you donate once to every vertex. Find the smallest initial amount of money W that enables you to win the game.

Constraints

• 1 \leq N \leq 10^5
• N-1 \leq M \leq 10^5
• 1 \leq A_i,B_i \leq 10^9
• 1 \leq U_i < V_i \leq N
• The given graph is connected and simple (there is at most one edge between any pair of vertices).

Sample Input 1

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

Sample Output 1

6

If you have 6 yen initially, you can win the game as follows:

• Stand on Vertex 4. This is possible since you have not less than 6 yen.
• Donate 2 yen to Vertex 4. Now you have 4 yen.
• Move to Vertex 3. This is possible since you have not less than 4 yen.
• Donate 1 yen to Vertex 3. Now you have 3 yen.
• Move to Vertex 2. This is possible since you have not less than 1 yen.
• Move to Vertex 1. This is possible since you have not less than 3 yen.
• Donate 1 yen to Vertex 1. Now you have 2 yen.
• Move to Vertex 2. This is possible since you have not less than 1 yen.
• Donate 2 yen to Vertex 2. Now you have 0 yen.

If you have less than 6 yen initially, you cannot win the game. Thus, the answer is 6.

Sample Input 2

5 8
6 4
15 13
15 19
15 1
20 7
1 3
1 4
1 5
2 3
2 4
2 5
3 5
4 5

Sample Output 2

44

Sample Input 3

9 10
131 2
98 79
242 32
231 38
382 82
224 22
140 88
209 70
164 64
6 8
1 6
1 4
1 3
4 7
4 9
3 7
3 9
5 9
2 5

Sample Output 3

582