The internship team holds a lottery at various events.
The organizers choose 10 distinct random numbers from 1 to 32. Each participant gets a lottery ticket containing 6 distinct numbers from 1 to 32. A ticket is considered to be winning if it contains at least 3 numbers chosen by the organizers.
Help Yulia and write a program that will determine which ticket is winning.
The first input line contains 10 distinct integers ai (1 ≤ ai ≤ 32), the numbers chosen by the organizers.
The second line contains one integer n (1 ≤ n ≤ 1000), the number of the lottery tickets issued at the event.
Each of the next n lines contains 6 distinct integers bj (1 ≤ bj ≤ 32), the numbers written on the respective lottery ticket.
Print n lines. For each lottery ticket (in the order they appear in the input) output a line contains Lucky, if the ticket is considered to be winning, otherwise output a line contains Unlucky.
1 2 3 4 5 6 7 8 9 32
3
1 2 10 11 12 13
1 2 3 10 11 12
32 1 10 20 30 3
Unlucky
Lucky
Lucky
Vladislav invented a new algorithm of the distributed key construction.
The distributed key consists of 2n numerical sequences of length n. To construct the key Vladislav gets some permutation p of length n2. Next step is to put the elements of p into a square matrix a. The first n elements of p form the first row of a, next n elements form the second row, etc. Finally, 2n numerical sequences of the distributed key are rows and columns of the matrix a.
These 2n sequences were given to Vladislav in some arbitrary order. He spent a while trying to come up with an algorithm for recovering the permutation. Try to restore the permutation before the end of the round!
The first input line contains one integer n (1 ≤ n ≤ 100).
Each of the next 2n lines contains n integers from 1 to n2, rows and columns of the matrix a in some order.
It is guaranteed that the input is correct, there is at least one suitable permutation p.
Print a permutation p of integers from 1 to n2.
2
1 2
1 3
2 4
3 4
1 2 3 4
4
1 6 14 7
5 4 1 13
13 16 12 10
8 3 6 16
11 2 7 10
15 9 14 12
4 3 9 2
5 8 15 11
5 4 1 13 8 3 6 16 15 9 14 12 11 2 7 10
Victor usually spends free time with reading books, solving riddles and puzzles.
Yesterday he decided to come up with his own puzzle. One should fill the table of size n × n with integers from 1 to n in a such way that the sum of the numbers in each row and the sum of numbers in each column is divisible by n. Each integer from 1 to n can be used arbitrary number of times.
Help Victor to determine the number of distinct tables satisfying the requirements of the puzzle. Two table are considered to be distinct if they differ in at least one cell. As the number Victor wants to compute may be pretty big, you only need to find its remainder modulo 109 + 7.
The only input line contains a single integer n (1 ≤ n ≤ 1000), the number of row and the number of columns of the table.
Print the number of appropriate tables modulo 1 000 000 007.
2
2
3
81
Little Andrey wants to work in IT. He already knows that he should exercise in mathematics and algorithms.
Andrey likes to play with a set of wooden sticks of various lengths. Experimentally he found that three sticks can form a triangle, if the length of the longest of them is strictly less than the sum of two others.
A sequence of n sticks is located on the table. Andrey chooses some interval with indices from l to r and looks for three sticks which can form a triangle.
Help Andrew, for each of the q intervals find three sticks such that he can make a triangle.
The first input line contains two integers n and q (1 ≤ n, q ≤ 300 000), number of sticks and number of intervals. The second line contains n integers li (1 ≤ li ≤ 1018), the array of sticks length in the order they lie on the table.
Each of the next q lines contains two integers l and r (1 ≤ l ≤ r ≤ n), the interval boundaries.
For each interval print any three different indices i j k (l ≤ i, j, k ≤ r) such that sticks with lengths li lj lk make a triangle. If there are no such indices, output the only number - 1.
5 3
1 3 1 3 1
1 3
2 4
1 5
-1
2 3 4
1 3 5
9 3
3 4 5 3 4 7 3 4 8
1 3
4 6
7 9
1 2 3
-1
-1
5 2
1 2 3 4 5
1 1
2 3
-1
-1
One of the most important component of a good search engine is the informative snippets of the documents.
Snippet management is a feature of some text editors, program source code editors, IDEs, and related software. It allows the user to avoid repetitive typing in the course of routine edit operations.
Vladimir is working on a snippets project. Vladimir's algorithm selects the most appropriate snippet for the document, but it only considers such parts of the document that contain words that occur in the query.
You are given a sequence of words w1, w2, ..., wn and the set of words s1, s2, ..., sk (different words from the query). Find the number of pairs of indices (l, r) (1 ≤ l ≤ r ≤ n) such that among the words wl, wl + 1, ..., wr there are all query words si. We say that word si occurs on the segment from l to r if and only if there exits j, such that wj = si and l ≤ j ≤ r. That is, we count only exact matches and do not consider substrings.
The first input line contains two integers n and k (1 ≤ n, k ≤ 100 000), the number of words in the document and the number of words in the query, respectively. The second line contains n words wi (1 ≤ |wi| ≤ 10). The third line contains k different words si (1 ≤ |si| ≤ 10).
The words in the lines are separated by single spaces. The words consist of lowercase English letters.
In a single line print the number of pairs of indices satisfying the problem.
6 2
yandex search engine algorithm is powerful
yandex algorithm
3
9 1
the best solution is trying to find better solution
solution
27
7 2
a b a c a b a
b a
18
The Alexander's distributed computational system consists of n computers which are connected in a network with n - 1 wires. Each pair of computers is directly or indirectly (via other computers) connected by these wires.
Alexander is worried about the safety of the data in the system. He plans to add the extra HDDs into two storage computers. The distance between two computers is the minimum possible number of wires that is required to get data from one computer to the other. When Alexander picks two computers, for each computer in his network he computes the minimum possible distance to the storage. Unreliability of the whole network is equal to the maximum value of this minimum distance among all computers in the network.
Help Alexander and find two different computers which should be used to install additional hard drives in order to achieve minimum value of unreliability.
The first input line contains one integer n (2 ≤ n ≤ 200 000), number of computers in the Alexander's system. Each of the next n - 1 lines contains two integers x y (1 ≤ x, y ≤ n, x ≠ y), the indices of computers connected by the direct connection.
Print the indices of two different selected computers. If there are multiple correct solutions, print any of them.
3
1 2
2 3
3 1
6
1 2
3 2
2 4
4 5
4 6
2 4