You are given an array a consisting of n integers. A subarray (l, r) from array a is defined as non-empty sequence of consecutive elements al, al + 1, ..., ar.
The beauty of a subarray (l, r) is calculated as the bitwise AND for all elements in the subarray:
Your task is to calculate the summation of the beauty of all subarrays (l, r) (1 ≤ l ≤ r ≤ n):
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 105), where n is the size of the array a.
The second line of each test case contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106), giving the array a.
For each test case, print a single line containing the summation of the beauty of all subarrays in the given array.
2
3
7 11 9
4
11 9 6 11
40
48
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.
A bitwise AND takes two equal-length binary representations and performs the logical AND operation on each pair of the corresponding bits, by multiplying them. Thus, if both bits in the compared position are 1, the bit in the resulting binary representation is 1 (1 × 1 = 1); otherwise, the result is 0 (1 × 0 = 0 and 0 × 0 = 0). This operation exists in all modern programming languages, for example in language C++ and Java it is marked as &.
In the first test case, the answer is calculated as summation of 6 subarrays as follow:
You are given an array a consisting of n elements a1, a2, ..., an. Array a has a special property, which is:
You are given the array a with some lost elements from it, each lost element is replaced by -1. Your task is to find all the lost elements again, can you?
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains two integers n and m (1 ≤ n ≤ 1000) (1 ≤ m ≤ 109), where n is the size of the array, and m is the described modulus in the problem statement.
The second line of each test case contains n integers a1, a2, ..., an ( - 1 ≤ ai < m), giving the array a. If the ith element is lost, then ai will be -1. Otherwise, ai will be a non-negative integer less than m.
It is guaranteed that the input is correct, and there is at least one non-lost element in the given array.
For each test case, print a single line containing n integers a1, a2, ..., an, giving the array a after finding all the lost elements.
It is guaranteed that an answer exists for the given input.
4
5 10
1 2 3 4 5
4 10
7 -1 9 -1
6 7
5 -1 -1 1 2 3
6 10
5 -1 7 -1 9 0
1 2 3 4 5
7 8 9 0
5 6 0 1 2 3
5 6 7 8 9 0
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.
You are given an array a consisting of n element a1, a2, ..., an. For each element ai you must find another element aj (i ≠ j), such that the summation of ai and aj mod (109 + 7) (i.e. (ai + aj) % (109 + 7)) is as maximal as possible.
Can you help judges by solving this hard problem?
The first line contains an integer T, where T is the number of test cases.
The first line of each test contains an integer n (2 ≤ n ≤ 105), where n is the size of the array a.
The second line of each test case contains n integers a1, a2, ..., an (0 ≤ ai < 109 + 7), giving the array a.
For each test case, print a single line containing n space separated elements, such that the ith element is the answer to the ith element in the array a (i.e. the maximum value of (ai + aj) % (109 + 7)).
2
3
1 2 3
2
1000000000 1000000000
4 5 5
999999993 999999993
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.
Yousef has a string s that is used to build a magical string w by repeating the string s infinitely many times. For example, if s = aabbb , then w = aabbbaabbbaabbbaabbb....
Mohammad always claims that his memory is strong, and that his ability to count is very high, so Yousef decided to hold a test for Mohammad, in order to know the truth of his claims.
Yousef will give Mohammad q queries, such that each query consisting of two integers l and r, and a lowercase English letter c. The answer of each query is how many times the letter c appears between the lth and rth letters in string w.
Mohammad must answer all the queries correctly, in order to proof his claims, but currently he is busy finishing his meal. Can you help Mohammad by answering all queries?
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains two integers n and q (1 ≤ n ≤ 104) (1 ≤ q ≤ 105), where n is the length of string s, and q is the number of queries.
The second line of each test case contains the string s of length n consisting only of lowercase English letters.
Then q lines follow, each line contains two integers l and r and a lowercase English letter c (1 ≤ l ≤ r ≤ 109), giving the queries.
For each query, print a single line containing how many times the letter c appears between the lth and rth letters in string w.
1
8 5
abcabdca
1 8 c
1 15 b
4 9 a
5 25 d
2 7 c
2
4
3
3
2
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.
It is always fun to play with dice, here is one interesting game:
You are given n fair dice with 6 faces, the faces does not necessarily have values from 1 to 6 written on them. instead, they can have any values from 1 to 100 written on them.
Suppose you threw the n dice one after another, let us define the result of the throws as the multiplication of the numbers you get from each dice mod 109 + 7.
You task is to find how many different ways you can get the result of the dice throws equal to x.
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains two integers n and x (1 ≤ n ≤ 14) (0 ≤ x < 109 + 7), where n is the number of the dice and x is the required result from the throws.
Then n lines follow, the ith line contains 6 integers fi1, fi2, ..., fi6 (1 ≤ fij ≤ 100), giving the values of ith dice's faces.
For each test case, print a single line containing how many different ways you can get the result of the dice throws equal to x
3
3 9
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
5 6
1 2 9 9 9 9
1 2 9 9 9 9
1 3 9 9 9 9
1 3 9 9 9 9
1 6 9 9 9 9
5 999999937
100 1 1 1 1 1
100 1 1 1 1 1
100 1 1 1 1 1
100 1 1 1 1 1
100 1 1 1 1 1
3
5
1
You are given a set of n strings such that all characters in the strings are 'a', 'b', or 'c'.
Also, you are given q queries, such that each query consisting of two strings a and b. The answer of each query is the index of the string with the most number of palindrome substrings between strings a and b from the given set.
A substring of the string s is a sequence sl, sl + 1, ..., sr for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), where n is the length of the string s.
A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as "madam" or "racecar".
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains two integers n and q (1 ≤ n ≤ 104) (1 ≤ q ≤ 105), where n is the number of strings, and q is the number of queries.
Then n lines follow, each line contains a non-empty string with length no more than 30, giving the strings. All characters in the strings are 'a', 'b', or 'c'. It is guaranteed that all strings are unique. The given strings are numbered from 1 to n.
Then q lines follow, each line contains two strings a and b, giving the queries. It is guaranteed that strings a and b exist in the given set of strings.
For each query, print a single line containing the index of the string with the most number of palindrome substrings between the given strings a and b. If there are more than one answer, print the lowest index.
1
5 5
aaaaa
abaabc
cbbaca
abccba
abca
aaaaa abca
cbbaca abccba
abaabc abccba
abccba abca
abaabc abccba
1
4
2
4
2
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.
Alaa sometimes feels bored at work, so at such times she starts playing with a beautiful array a consisting of n integers a1, a2, ..., an.
Alaa starts counting the number of magical indices in the array a. An index x is said to be magical if it satisfying the following rules:
Can you help Alaa by counting the number of magical indices in the array a.
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 106), where n is the size of the array a.
The second line of each test case contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106), giving the array a.
For each test case, print a single line containing the number of magical indices in the array a.
2
8
2 1 3 4 6 5 7 9
6
4 2 7 9 8 10
3
1
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.
Husam has a lot of free time, so he is using this time in repairing corrupted binary images.
A Binary image can be represented as 2-dimensional array consisting of n rows, each of which is divided into m columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to m from left to right. Each cell is identified by a pair (x, y), which means that the cell is located at row x and column y. The possible values in the binary images are either zero or one.
A binary image is good if all cells in the first row, last row, first column, and last column are ones. Otherwise, the binary image is corrupted. If the binary image is corrupted, Husam will fix it.
Husam wants to fix the image with the minimum number of moves, such that in each move he can swap the values at two different cells.
Can you help Husam by calculating the minimum number of required moves to fix the image?
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains two integers n and m (3 ≤ n, m ≤ 50), where n is the number of rows in the binary image, and m is the number of columns in each row.
Then n lines follow, each line contains m characters, giving the binary image. All values in the binary image are either zero or one.
For each test case, print a single line containing -1 if Husam cannot fix the binary image. Otherwise, print the minimum number of required moves to fix the image.
3
3 3
111
101
111
4 4
1111
0111
1000
1111
4 5
10101
01010
10101
01010
0
2
-1
In the first test case, the image is good. In the second test case, Husam needs to swap the values of cells (2, 1) and (2, 2), and swap the values of cells (2, 3) and (3, 4), in order to fix the image.
Universal Studios Theme Parks announced a new game named The Crazy Jumper, that is targeted problem solving fans.
In this game, there are n large boxes numbered from 1 to n from left to right, such that the ith box (1 < i ≤ n) is located to the right of the (i - 1)th box. Each box has a color, such that ci is the color of the ith box.
The goal of the game is to reach the nth box starting from the 1st box, by jumping between the boxes. The player can do one of the following jumps:
Ziad will be the first one to play the game, but he is not sure whether the game is amusing or not, so he wants to finish it with the minimum number of jumps. Can you help Ziad by telling him what is the minimum number of required jumps to reach the nth box stating from the 1st box?
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 2 × 105), where n is the number of the boxes in the game.
The second line of each test case contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 2 × 105), where ci is the color of the ith box.
For each test case, print a single line containing the minimum number of required jumps to reach the nth box starting from the 1st box.
3
6
9 2 4 7 1 5
5
1 2 1 1 4
6
1 2 3 1 3 2
5
3
2
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.
Since the problem set was hard, here is an easy task for you to solve.
You are given an array a consisting of n integers, and your task is to calculate the summation of the multiplication of all subsets of array a. (See the note for more clarifications)
A subset of an array a is defined as a set of elements that can be obtained by deleting zero or more elements from the original array a.
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 105), where n is the size of array a.
The second line of each test case contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106), giving the array a.
For each test case, print a single line containing the summation of the multiplication of all subsets of array a. Since this number may be too large, print the answer modulo 109 + 7.
3
3
1 2 3
2
3 5
1
4512
23
23
4512
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.
In the first test case, the array a has 6 subsets, and the answer is calculated as follow:
An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once, such as "post", "stop", and "spot".
You are given a string s consisting of lowercase English letters. Your task is to count how many distinct anagrams of the string s are palindromes.
A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as "madam" or "racecar".
For example, "aabb" has 6 distinct anagrams, which are: "aabb", "abab", "abba", "baab", "baba", "bbaa". Two of the previous anagrams are palindromes, which are: "abba", "baab".
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 20), where n is the length of the string s.
The second line of each test contains a string s of length n consisting of lowercase English letters.
For each test case, print a single line containing how many distinct anagrams of the string s are palindromes.
5
4
aabb
6
ababbc
6
abaaba
12
babacbcbcaca
14
aaaabbcaaaabbc
2
0
3
90
105