There is a fight between a boss and his 3 employees. But instead of firing, the boss invites them to a judo fight. As if that was not enough, he says that 2 employees can come together to fight him. If we define the power of the 3 employees as P1,P2 and P3, and W is the power of the boss. Now, the fight is won by the team which has higher total combined power. In case of same power, the employees win. You need to check if the employees can win or not.
The input contains 4 lines of input: P1, P2, P3 and W in this order only.
Output a single word: "YES" if the employees can win, "NO" otherwise. Don't print the quotes in the output.
1
2
3
7
NO
Given two equally sized arrays A and B of size N. A is empty and B has some values.
You need to fill A with an element X such that X belongs to B.
The only operations allowed are:
1. Copy B[i] to A[i].
2. Cyclic shift B by 1 to the the right.
You need to minimise the number of operations.
The first line contains a single positive integer N(1 ≤ N ≤ 106), denoting the size of the arrays.
Next line contains N space separated positive integers denoting the elements of the array B(1 ≤ B[i] ≤ 105).
Output a single integer, denoting the minimum number of operations required.
3
1 2 3
5
6
1 1 2 2 3 3
10
In the first test case:
We can have 5 steps as: fill first element, shift, fill second element, shift, fill third element.
Initially, A = [_, _, _], B = [1, 2, 3]
After step 1, A = [1, _, _], B = [1, 2, 3]
After step 2, A = [1, _, _], B = [3, 1, 2]
After step 3, A = [1, 1, _], B = [3, 1, 2]
After step 4, A = [1, 1, _], B = [2, 3, 1]
After step 5, A = [1, 1, 1], B = [2, 3, 1]
You live in a graph G, with N vertices and M edges. P of these vertices have gangsters living on them. You owe each gangster some money, given by the array C (of size P). You wish to travel from s to t. If you step within distance k of any gangster who you haven't paid, you die. We define the length of a path as then number of edges it comprises. We define the distance of two nodes as the length of the shortest path connecting them. Further, we define the cost of travelling as the sum of gangster debts you pay off. Of course, you wish to minimise the cost of travelling from s to t without dying. Note that you may not die at s or t either.
First line contains four integers, N, M, P, and K. (1 ≤ N, M, K ≤ 105, 1 ≤ P ≤ 10) Second line contains P integers, the locations of the gangsters. Third line contains P integers, the array C (1 ≤ Ci ≤ 109) Each of the next M line contains two integers, xi and yi, which mean that there exists an edge between the nodes xi and yi. The last line contains two integers, s and t, the source and the target. It is guaranteed that a solution always exists.
A single integer, the minimum cost of travelling from s to t.
5 5 1 1
4
100
1 2
2 3
3 4
3 5
4 5
1 5
100
For the given example, the graph looks like 
Note that the gangster is at distance 1 from the nodes 5 and 3, both of which must be visited.
You are given two arrays, A and B, both of size N. You are given Q queries of the form (i, j, k). Where for each query, you have to find the cardinality of the multiset 
.
First line contains two integers, N, and Q (1 ≤ N, Q ≤ 105). The next line contains N integers, the array A (1 ≤ Ai ≤ 109). The next line contains N integers, the array B (1 ≤ Bi ≤ 109). Each of the next Q lines contains three integers, i, j and k (1 ≤ i ≤ j ≤ N, 1 ≤ K ≤ 105), which represent a query as defined in the statement.
Q lines, each containing the answer to one query.
5 1
1 1 1 1 1
1 1 1 1 1
1 5 1
25
Consider a numeric string str where stri denotes the digit(0 to 9) at index i. We call (x1, x2, x3, x4) quadruple a palindromic quadruple of string S if it satisfies the following criteria : Sx1 = Sx4 and Sx2 = Sx3 where x1 < x2 < x3 < x4.
You are given Q queries where each query is of form :
- 1 i j: Print number of different palindromic quadruples (x1, x2, x3, x4) for string str such that i ≤ x1 < x2 < x3 < x4 ≤ j. As the result can be large, print it modulo 109 + 7.
- 2 idx ch: Replace stridx with character ch.
The first line contains a string str, such that 
, and 
. The second line contains a single integer, Q(1 ≤ Q ≤ 105), the number of queries. Each of the next Q lines contains a query, with format as described in the problem statement. In queries of type 2, 
.
An integer for each query of type 1, one on each line.
01010
5
1 1 5
2 2 0
1 1 5
2 4 0
1 1 5
1
1
5
In the sample test case
- Query 1: The String is 01010, Possible palindromic quadruples = 0110, so answer = 1
- Query 2: Update str2 = 0, so the string is now 00010
- Query 3: The String is 00010, Possible palindromic quadruples = 0000, so answer = 1
- Query 4: Update str4 = 0, so the string is now 00000
- Query 5: The String is 00000, Possible palindromic quadruples is 0000 which can be selected in 5 ways, so answer = 5
Given a weighted undirected tree of N nodes, rooted at the node 1. You can remove at most 1 edge and add another edge of same weight such that the resulting graph is still a tree. Minimize the sum of distances from node 1 to all other nodes.
The first line contains a single integer N, the size of the tree. Next N - 1 lines contain three space separated integers u, v and w, denoting an edge between the vertices u and v of weight w.
Constraints: 1 ≤ N ≤ 5 × 104, 1 ≤ u, v ≤ N, - 103 ≤ w ≤ 103
Output a single integer, the minimum sum of distances from node 1 to all other nodes.
2
1 2 3
3
4
1 2 61
1 3 -14
3 4 -47
-75