You are given a directed tree with N with nodes numbered 1 to N and rooted at node 1. Each node initially contains 0 coins.
You have to handle a total of M operations:
- 1 L Y : Increase by Y the coins of all nodes which are at a distance L from root.
- 2 X : Report the sum of coins of all nodes in subtree rooted at node X.
First line contains N and M. Each of the next N - 1 lines contains u and v denoting directed edge from node numbered u to v.
Each of the next M lines contain queries of either Type 1 or 2.
For each query of Type 2, print the required sum.
Constraints
- 1 ≤ N ≤ 105
- 1 ≤ M ≤ 104
- 0 ≤ L ≤ Maximum height of tree
- 0 ≤ Y ≤ 109
- 1 ≤ X, u, v ≤ N
5 4
1 2
1 3
3 4
3 5
1 1 2
1 2 3
2 3
2 1
8
10
In first update nodes 2 and 3 are increased by 2 coins each.
In second update nodes 4 and 5 are increased by 3 each.
Given two times when seen on a digital clock, count the number of moments between these two times (both start and end time included) when the time was a palindrome.
A digital clock shows time in the format HH:MM:SS (hours:minutes:seconds).
For example, 2:40:38 pm is represented as 14:40:38.
The first line contains q ( ≤ 105) queries. This is followed by q lines each containing two time strings, t1 and t2, which are 6 digit integers that represent times shown by a digital clock. It is ensured that t1 and t2 are valid times(t1 occurs on or before t2).
For each query in one line print the number of palindromic times.
4
00:00:01 00:00:01
09:09:09 13:34:57
11:11:11 11:11:11
02:38:15 03:01:16
0
22
1
3
Query 1: Only 1 moment is considered in this case, i.e., 00:00:01. We can clearly see that 00:00:01 is not a palindromic string.
Query 4: Between 02:38:15 and 03:01:16, there are 3 moments that are palindromic strings. They are 02:44:20, 02:55:20 and 03:00:30.
Note that the time as seen on a digital clock should appear as a palindrome. 1 is a palindrome, but 00:00:01 on a digital clock is not.
Alice had a bag where each number from 1 to N was present in it. After a magic trick she either removes all even numbers or all odd numbers from the bag. Given the kind of trick she has performed find the P’th smallest number in the bag after the trick. For example P = 1 denotes the smallest number present.
First line contains T, the number of test cases. Each test case consists of N, a string S and an integer P in single line.
S will be either "odd" or "even"(quotes for clarity), denoting the kind of trick Alice has performed.
Note: It is guaranteed that P will be less than or equal to remaining items in the bag.
For each test case print required answer in one line.
Constraints
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 103
2
4 odd 2
5 even 2
4
3
Example 1.
After performing the “odd” trick the numbers 1 and 3 get removed from the bag. Numbers 2 and 4 are left in the bag. 2nd smallest number is 4 now.
Example 2.
After performing the “even” trick the numbers 2 and 4 get removed from the bag. Numbers 1, 3 and 5 are left in the bag. 2nd smallest number is 3 now.
Frodo Baggins is trying to run from the fury of Smaug. Let’s assume we represent our city by a weighted undirected connected graph(with no self-loops and multi-edges) with N nodes and N edges.
You will be given Q queries of form St, De, S, Vf, VS which denotes:
Frodo is currently at node St and needs to reach node De. He moves with constant velocity Vf. Smaug is currently at node S and he moves with constant velocity VS. Print "YES"(quotes for clarity), if Frodo can reach destination without being caught by Smaug no matter what path Smaug takes. Else print "NO"(quotes for clarity).
Note: If Frodo reaches at destination at same time as Smaug, print "NO".
First line contains N and Q, the number of nodes and number of queries respectively. Each of the next N lines contain integers u, v and w denoting an undirected edge between nodes numbered u and v, w being the weight of the edge.
Each of the next Q lines contain queries.
For each query print the required answer in one line.
Constraints
- 1 ≤ N, Q ≤ 105
- 1 ≤ u, v, St, De, S ≤ N
- 1 ≤ VF, VS, w ≤ 1000
5 2
1 2 2
2 3 3
3 4 7
4 5 5
5 1 6
1 3 5 1 2
2 4 5 2 2
YES
NO
Alice writes a permutation P1, P2, P3, ... PN of [1, 2, 3, ...N]. A permutation that follows the condition:
Pi > Pi / 2 for all i = 2 to N, is assumed to be an ‘amusing’ permutation. Note that / denotes integer division.
Alice wrote down all ‘amusing’ permutations on a sheet of paper. For each number from i = 1 to N, she defines a set Si. A number j belongs to Si if number i was at j’th position in at-least one of the ‘amusing’ permutations.
You have to find how many distinct Si exist for i = 1 to N.
First line contains T, the number of test cases. Each test case consists of N in single line.
For each test case, print the required answer in one line.
Constraints
- 1 ≤ T ≤ 104
- 1 ≤ N ≤ 1018
2
2
3
2
2
Example 1. Only ‘amusing’ permutations is [1, 2]. [2, 1] is not an ‘amusing’ permutation because P2 < P2 / 2.
S1 is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations. Similarly S2 is defined as {2}.
Therefore 2 distinct sets are possible ie. {1} and {2}.
Example 2. All ‘amusing’ permutations are: [1, 2, 3] and [1, 3, 2].
S1 is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations. Similarly S2 is defined as {2, 3} and S3 is also defined as {2, 3}.
So a total of 2 distinct sets {1} and {2, 3} are possible.
You have a N x M matrix of cells. The cell (i, j) represents the cell at row i and column j. You can go from one cell (i, j) only down or right, that is to cells (i + 1, j) or (i, j + 1).
But K cells are blocked in the matrix(you can’t visit a blocked cell). You are given coordinates of all these cells.
You have to count number of ways to reach cell (N, M) if you begin at cell (1, 1).
Two ways are same if and only if path taken is exactly same in both ways.
First line consists of T, denoting the number of test cases. Each test case consists of N, M and K in single line. Each of the next K lines contains two space separated integers (xi, yi), denoting the blocked cell’s coordinates.
For each test case print the required answer modulo 109 + 7 in one line.
Constraints
- 1 ≤ T ≤ 10
- 1 ≤ N, M ≤ 105
- 0 ≤ K ≤ 103
- 1 ≤ xi ≤ N
- 1 ≤ yi ≤ M
2
3 2 0
2 3 1
1 2
3
1
Example test case 1:
No cell is blocked. 3 distinct paths are:
- (1, 1) to (1, 2) to (2, 2) to (3, 2).
- (1, 1) to (2, 1) to (2, 2) to (3, 2).
- (1, 1) to (2, 1) to (3, 1) to (3, 2).
Example test case 2: Only one valid path:
- (1, 1) to (2, 1) to (2, 2) to (2, 3).
Given N and K, count number of permutations of [1, 2, 3...N] in which no two adjacent elements differ by more than K. For example, permutation [4, 1, 2, 3] cannot be counted for 
.
First line contains T(1 ≤ T ≤ 10), the number of test cases. Each test case consists of N(1 ≤ N ≤ 15) and K(0 ≤ N) in single line.
For each test case print the required answer in one line.
2
2 1
3 1
2
2
Example case 1. All permutations are valid.
Example case 2. Permutations [1, 2, 3], [3, 2, 1] are counted.
Given an array of N integers A1, A2 ... AN and an integer K, count number of subarrays of A such that number of inversions in those subarrays is at least K.
Inversions in a subarray Ai, Ai + 1,..., Aj is defined as number of pairs (a, b) such that i ≤ a < b ≤ j and Aa > Ab.
First line consists of N and K in single line. Next line contains N space separated integers denoting array A.
Print the required answer in one line.
Constraints
- 1 ≤ N ≤ 105
- 0 ≤ Ai ≤ 109
- 0 ≤ K ≤ N * (N - 1) / 2
4 1
1 2 4 0
3
2 0
1 2
3
Let’s denote by A[i, j] the subarray Ai, Ai + 1 ... Aj.
Example 1. A[1, 4], A[2, 4], A[3, 4] have at least 1 inversion.
Example 2. All subarrays are valid.
Little Toojee was a happy go lucky boy. He seemed to find most, if not all, things funny. One day he read a word and started laughing a lot. Turns out that the word consisted only of the letters L and O. Whenever he saw the subsequence ‘LOL’ in the word, he laughed for 1 second. Given t strings, find out for how long Toojee laughed on seeing each string.
The first line contains t queries. This is followed by t lines each containing one string S. String S consists only of capital alphabets.
Output for each string on a new line.
Constraints
- 1 ≤ t ≤ 10
- 1 ≤ |S| ≤ 105
2
LOL
LOLOL
1
4
Test1: On observation, we can tell that there is only 1 occurrence of LOL.
Test2: Let the string be 0-indexed and let V = {a, b, c} denote the indices that make up the string “LOL”, where a is index of the 1st ‘L’, b is index of the ‘O’ and c is the index of the 2nd ‘L’. So, V can be {0, 1, 2}, {2, 3, 4}, {0, 1, 4} and {0, 3, 4}. We see that there are 4 occurrences of the string “LOL”.
This time Laltu wanted the question to be straightforward. So, given 3 1-indexed sorted arrays (A[], B[], C[]), find the number of triplets 1 ≤ i ≤ j ≤ k, such that: A[i] ≤ B[j] ≤ C[k]. Note that i, j and k don’t exceed the size of respective arrays.
For example, Arrays: A = [1, 2, 3, 4] B = [5, 6, 7, 8] C = [9, 10, 11, 12]
The triplet (i, j, k) = (1, 2, 3) has to be considered because: A[1] ≤ B[2] ≤ C[3].
First line contains T, the number of test cases. Each test case consists of: P, the length of first array. The next line will consist of P integers. Q, the length of second array. The next line will consist of Q integers. R, the length of third array. The next line will consist of R integers.
For each test case print the required answer in one line.
Constraints
- 1 ≤ T ≤ 3
- 1 ≤ P, Q, R ≤ 105
- - 109 ≤ Elements of arrays ≤ 109
1
3
1 5 6
3
2 3 4
3
7 8 9
6
The possible triplets (i, j, k) are: (1, 1, 1) (1, 1, 2) (1, 1, 3) (1, 2, 2) (1, 2, 3) (1, 3, 3)
A thief is trying to escape the holds of the police through a city. Let’s assume we represent our city by a weighted undirected connected graph(with no self-loops and multi-edges) with N nodes and M edges.
Thief is currently at vertex numbered S and needs to reach vertex numbered D. Thief moves with constant speed VT = 1.
K policemen are initially located in K distinct locations denoted by A1, A2, ..., AK. Each policeman has a constant speed of VP = 1.
To help policemen, a single power booster have been provided to them. This power booster can be availed once from any one of the Q distinct ‘special’ nodes B1, B2, ..., BQ. Property of this power booster being that it doubles the speed of the policeman who avails this power booster.
Note: A policeman can choose not to avail the power booster even if he is at a ‘special’ node.
You have to print the shortest time in which thief can escape the police regardless of whatever path the police might take. If he can’t reach the destination, output - 1.
First line contains N and M, the number of nodes and number of edges respectively.
Each of the next M lines contain integers u v and w denoting an undirected edge between nodes numbered u and v, w being the weight of the edge. Next line contains a single integer K denoting number of different policemen. Next line contains K space separated integers denoting the distinct locations A1, A2, ..., AK.
Next line contains a single integer Q denoting number of ‘special’ nodes. Next line contains Q distinct space separated integers denoting the locations B1, B2, ..., BQ.
Next line contains two distinct integers S and D denoting the source and destination of the thief.
For each test case print the minimum time required for thief to escape(if possible). Else, output - 1.
Constraints
- 1 ≤ N ≤ 105
- M ≤ min(2 * 105, N * (N - 1) / 2)
- 0 ≤ u, v, S, D, Ai, Bi < N
- 0 ≤ Y ≤ 109
- 1 ≤ X, u, v ≤ N
- 0 ≤ K, Q ≤ N
- 1 ≤ w ≤ 109
4 4
0 1 2
1 2 4
2 3 10
3 0 2
1
3
1
0
2 1
-1
4 3
0 1 2
1 2 8
1 3 10
2
2 3
2
2 3
0 1
2
Example1:
Police takes the path 3 to 0 to 1 availing the power booster at node 0. Even though both policeman and thief reach the destination at same time, police catches thief.
Example2:
Whichever policeman uses the power booster, thief will be able to escape in 2 seconds.