Hasan and Bahosain want to buy a new video game, they want to share the expenses. Hasan has a set of N coins and Bahosain has a set of M coins. The video game costs W JDs. Find the number of ways in which they can pay exactly W JDs such that the difference between what each of them payed doesn’t exceed K.
In other words, find the number of ways in which Hasan can choose a subset of sum S1 and Bahosain can choose a subset of sum S2 such that S1 + S2 = W and |S1 - S2| ≤ K.
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains four integers N, M, K and W (1 ≤ N, M ≤ 150) (0 ≤ K ≤ W) (1 ≤ W ≤ 15000), the number of coins Hasan has, the number of coins Bahosain has, the maximum difference between what each of them will pay, and the cost of the video game, respectively.
The second line contains N space-separated integers, each integer represents the value of one of Hasan’s coins.
The third line contains M space-separated integers, representing the values of Bahosain’s coins.
The values of the coins are between 1 and 100 (inclusive).
For each test case, print the number of ways modulo 109 + 7 on a single line.
2
4 3 5 18
2 3 4 1
10 5 5
2 1 20 20
10 30
50
2
0
Using at most 7 matchsticks, you can draw any of the 10 digits as in the following picture:
Zaytoonah has a number that consists of N digits. She wants to move some sticks (zero or more) to maximize the number. Note that she doesn’t want to remove any of the sticks, she will only move them from one place to another within the N digits. She also doesn’t want to add new digits as N is her lucky number.
Can you help Zaytoonah maximize her number?
The first line of input contains a single integer T, the number of test cases.
Each test case contains a single integer N (1 ≤ N ≤ 105), followed by a space, then N digits that represent the number Zaytoonah currently has.
For each test case, print on a single line the maximum number Zaytoonah can get.
3
1 3
3 512
3 079
5
977
997
Judge Bahosain was bored at ACM AmrahCPC 2016 as the winner of the contest had the first rank from the second hour until the end of the contest.
Bahosain is studying the results of the past contests to improve the problem sets he writes and make sure this won’t happen again.
Bahosain will provide you with the log file of each contest, your task is to find the first moment after which the winner of the contest doesn’t change.
The winner of the contest is the team with the highest points. If there’s more than one team with the same points, then the winner is the team with smallest team ID number.
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains two space-separated integers N and Q (1 ≤ N, Q ≤ 105), the number of teams and the number of events in the log file. Teams are numbered from 1 to N.
Each of the following Q lines represents an event in the form: X P, which means team number X (1 ≤ X ≤ N) got P ( - 100 ≤ P ≤ 100, P ≠ 0) points. Note that P can be negative, in this case it represents an unsuccessful hacking attempt.
Log events are given in the chronological order.
Initially, the score of each team is zero.
For each test case, if the winner of the contest never changes during the contest, print 0. Otherwise, print the number of the first event after which the winner of the contest didn’t change. Log events are numbered from 1 to Q in the given order.
1
5 7
4 5
3 4
2 1
1 10
4 8
3 -5
4 2
5
Given an R×C grid with each cell containing an integer, find the number of subrectangles in this grid that contain only one distinct integer; this means every cell in a subrectangle contains the same integer.
A subrectangle is defined by two cells: the top left cell (r1, c1), and the bottom-right cell (r2, c2) (1 ≤ r1 ≤ r2 ≤ R) (1 ≤ c1 ≤ c2 ≤ C), assuming that rows are numbered from top to bottom and columns are numbered from left to right.
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains two integers R and C (1 ≤ R, C ≤ 1000), the number of rows and the number of columns of the grid, respectively.
Each of the next R lines contains C integers between 1 and 109, representing the values in the row.
For each test case, print the answer on a single line.
1
3 3
3 3 1
3 3 1
2 2 5
16
Mr. Ya Rajaie has N books and wants to put them in bookshelves, each bookshelf can have at most 5 books. Find the minimum number of bookshelves needed to store the N books.
The first line of input contains a single integer T, the number of test cases.
Each test case contains a single integer N (1 ≤ N ≤ 109), the number of Ya’s books.
For each test case, print on a single line the minimum number of bookshelves needed to store the books.
2
7
15
2
3
Given a string of lowercase English letters. You are allowed to choose two letters that exist in any position in the string, replace all occurrences of the first letter you chose with the second one, and replace all occurrences of the second letter you chose with the first one.
Your task is to find the string that comes first in dictionary order among all possible strings that you can get by performing the above operation at most once.
For example, by exchanging letter ‘a’ with letter ‘h’ in string “hamza”, we can get string “ahmzh”.
The first line of input contains a single integer T, the number of test cases.
Each test case contains a non-empty string on a single line that contains no more than 105 lowercase English letters.
For each test case, print the required string on a single line.
3
hamza
racecar
mca
ahmzh
arcecra
acm
Jordanian notes are 1, 5, 10, 20, and 50 JDs.
Maram is going to the shop and has N JDs, she wants to have the money in a form that will allow her to pay for any single item exactly, which means without waiting for change. Given N and the price of each item in the shop, find the required form, that is, find the number of notes of each type she has to have before going to the shop.
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains two integers N and M (1 ≤ N, M ≤ 105), the amount of money Maram has and the number of items in the shop, respectively. The second line contains M space-separated integers, each value represents the price of an item and is between 1 and N.
For each test case, print five space-separated integers on a single line, where the first integer represents the number of notes of the first type (1 JD), the second integer represents the number of notes of the second type (5 JDs), and so on.
If there’s more than one possible form, find the one that minimizes the total number of notes.
Note that the total amount of money in the printed form should be equal to N.
2
150 4
150 123 70 20
212 3
1 200 61
5 1 0 2 2
2 0 1 0 4
Rami and K of his friends are going to watch a movie tonight. There are only one row that contains some available seats, all other rows are taken. Given the description of this row, Rami wants to know if he can find consecutive seats available to sit with his friends.
The first line of input contains a single integer T, the number of test cases.
The first line of each test case consists of two-separated integers C, K (1 ≤ C, K ≤ 105), the number of seats in the row and the number of friends going with Rami, respectively.
The second line contains a string of C digits, where 0 represents an empty seat, and 1 represents taken one.
For each test case, print a single line with yes if Rami can find a place for him and his friends, otherwise print no.
2
5 2
10101
6 3
000011
no
yes
SaMer is building a simple robot that can move in the four directions: up (^), down (v), left (<), and right (>). The robot receives the commands to move as a string and executes them sequentially. The robot skips the commands that make it go outside the table.
SaMer has an R×C table and a string of instructions. He wants to place the robot on some cell of the table without rotating it, such that the robot will skip the minimum number of instructions. Can you help him find the number of instructions that will be skipped by the robot if it was placed optimally?
The first line of input contains a single integer T, the number of test cases.
Each test case contains two space-separated integers R and C (1 ≤ R, C ≤ 105), the number of rows and the number of columns in the table, followed by a non-empty string of no more than 200000 characters representing the initial instructions. The instructions are executed in the given order from left to right.
For each test case, print the minimum number of instructions which will be skipped, on a single line.
2
2 2 >^<v>^^<v
3 4 >^<^vv<>v>>v
1
2
You are given an array A of integers of size N, and Q queries. For each query, you will be given a set of distinct integers S and two integers L and R that represent a range in the array. Your task is to count how many numbers in the given range are divisible by at least one number from the set.
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains two integers, N and Q (1 ≤ N, Q ≤ 105), the size of the array and the number of queries, respectively.
The next line contains N space-separated integers, the values of the array A (1 ≤ Ai ≤ 109).
Each of the next Q lines contain the description of one query in the form:
LRS
Where L and R (1 ≤ L ≤ R ≤ N) represent the range, and S is an integer between 1 and 1023 (inclusive) and represents the set; consider the binary representation of the number S, if the ith bit (1-based) is 1, then the number i belongs to the set. Since S is less than 1024, the values in the set are between 1 and 10.
For example: if S is equal to 6, the binary representation of 6 is 110, and this means the values in the set are 2 and 3.
The input was given in this way to reduce the size of the input file.
Print the answer for each query on a single line.
1
4 2
2 5 3 8
1 3 2
2 4 355
1
3
Consider a directed graph G of N nodes and all edges (u→v) such that u < v. It is clear that this graph doesn’t contain any cycles.
Your task is to find the lexicographically largest topological sort of the graph after removing a given list of edges.
A topological sort of a directed graph is a sequence that contains all nodes from 1 to N in some order such that each node appears in the sequence before all nodes reachable from it.
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains two integers N and M (1 ≤ N ≤ 105) 
, the number of nodes and the number of edges to be removed, respectively.
Each of the next M lines contains two integers a and b (1 ≤ a < b ≤ N), and represents an edge that should be removed from the graph.
No edge will appear in the list more than once.
For each test case, print N space-separated integers that represent the lexicographically largest topological sort of the graph after removing the given list of edges.
3
3 2
1 3
2 3
4 0
4 2
1 2
1 3
3 1 2
1 2 3 4
2 3 1 4
Reem likes to look up into the night sky and count how many stars there are. The sky is represented as a tree, and a star is a fixed node with three or more rays of possibly varying lengths leading out of it. A ray is a chain of connected nodes where each node except for the last one is connected to exactly two nodes, and the last one is connected to exactly one node.
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains a single integers N (1 ≤ N ≤ 105), the number of nodes in the sky.
Each of the next N - 1 lines contains two integers a and b (1 ≤ a, b ≤ N), and represents a link that connects two nodes.
It is guaranteed that the given graph is a tree.
For each test case, print the maximum number of stars Reem can get after removing zero or more nodes, on a single line.
1
9
1 2
3 2
5 1
3 7
1 4
3 8
1 6
3 9
2
A tree is an undirected graph with exactly one path between any two nodes.