Bagheera is getting bigger by the day; he is a big boy now. Rama always tries to get him the best food there is.
There are $$$n$$$ bags of food; the $$$i$$$-th bag has food with value $$$a_i$$$. Let's say that the value of bags she buys is the bitwise OR of food values in them.
Rama can only buy $$$n - 1$$$ bags of food, what's the maximum value of food she can buy?
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
The first line of each test case contains an integer $$$n$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$.
The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$.
For each test case, print an integer that represents the maximum value of food she can buy.
331 2 341 2 2 258 2 3 5 11
3 3 15
452 4 8 16 3272 4 8 16 32 64 12882 4 12 8 16 32 64 12881 2 4 8 16 32 64 127
60 252 254 127
1, 2, 3, ..., 9000 and 9001! It's over 9000! — Ahmad said while counting the number of problems he wrote about pairs.
You're given an array $$$a$$$ of $$$n$$$ integers; let's imagine a multiset $$$S$$$ containing all the absolute differences between any two elements $$$a_i$$$ and $$$a_j$$$ for all $$$1 \leq i, j \leq n$$$ and $$$i \neq j$$$.
Here, the absolute difference between two integers $$$x$$$ and $$$y$$$ is $$$|x - y|$$$.
What's the sum of the largest $$$m$$$ elements in the multiset $$$S$$$?
The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 2 \cdot 10^5; 1 \leq m \leq n \cdot (n - 1))$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^7)$$$.
For each test case, print one integer, the sum of the $$$m$$$ largest elements in the set $$$S$$$.
33 21 2 35 55 4 3 2 17 53 2 1 4 5 7 6
4 17 27
In the Amazon Fulfillment Center, there is a sequence of $$$n$$$ items; each item $$$i$$$ has two values, ID and a color.
As their manager, Hamza noticed that Ahmad and Bahaa were wasting a lot of time playing billiards in the fun area, so he decided to punish them.
He tasked them with finding the maximum size of a good package.
A package of size $$$k$$$ is considered good if it contains $$$k$$$ items with strictly increasing ID numbers and no two adjacent items share the same color.
Note: Items must be arranged in the same order as given in the input.
Can you help them finish the task?
The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
The first line of each test case contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$.
The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$, where $$$a_i$$$ is the ID of the $$$i_{th}$$$ item.
The third line of the test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ $$$(1 \leq b_i \leq 10^9)$$$, where $$$b_i$$$ is the color of the $$$i_{th}$$$ item.
It's guaranteed that the sum of $$$n$$$ over all test-cases doesn't exceed $$$10^5$$$.
For each test case, print a single integer representing the largest value of $$$k$$$ as described in the statement.
341 2 3 41 2 1 241 2 3 41 2 2 152 1 3 2 41 2 2 1 2
4 3 3
Ahmad, Hamza, Malek, and Bahaa were having a "break" at the beach (garage). They were discussing a problem Bahaa wrote, but it was too easy, so they started throwing ideas, and this is one of them.
In an Amazon Warehouse, there are $$$n$$$ items; the $$$i$$$-th item has a code $$$a_i$$$, and its price is $$$b_i$$$.
They have special pricing when you buy items in pairs. If you buy item $$$i$$$ and item $$$j$$$, the cost is $$$cost(i, j) = (a_i | a_j) \times b_j$$$.
For each item $$$i$$$, they're interested in calculating the following sum $$$$$$\sum_{j=1}^n cost(i, j)$$$$$$.
The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
The first line of each test case contains an integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$.
The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \leq a_i \lt 2^{15})$$$ .
The third line of the test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ $$$(1 \leq b_i \lt 2^{15})$$$.
It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.
For each test case, print $$$n$$$ integers; the $$$i$$$-th integer is the cost over all $$$j$$$-s for the $$$i$$$-th item.
331 2 31 2 333 2 11 2 342 4 8 155 3 10 4
16 16 18 18 16 12 188 222 226 330
Ahmad was trying to rob ideas for writing problems, but all the ideas were classic, so he decided to twist a problem just a little bit; it's more fun, right?
You're given a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters; you have to answer $$$q$$$ queries.
For each query, you will be given a string $$$t$$$ that you can reorder as you wish, and you have to find out if there is a substring in $$$s$$$ that is equal to $$$t$$$ after re-ordering its characters.
Note that you can only re-order characters in the string $$$t$$$.
The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$q$$$ $$$(1 \leq n, q \leq 10^5)$$$.
The second line of the test case contains a string $$$s$$$ consisting of $$$n$$$ lower case English letters.
The next $$$q$$$ lines of the test case each contain a string $$$t$$$ $$$(1 \leq t \leq n)$$$ consisting of lower case English letters.
It's guaranteed that the sum of $$$n$$$, $$$q$$$, and $$$|t|$$$ over all test cases doesn't exceed $$$10^5$$$.
For each query, print "YES" if you could find the string $$$t$$$, otherwise print "NO". "Yes", "YeS", "No" or any other casing will be accepted.
23 5aabaabaabababbba4 6abcdabcddbcabacdbdaccabacdd
YES YES YES NO NO YES YES YES YES YES NO
Ahmad has been reading a lot of blogs lately, and every time he sees two words next to each other starting with the same character he is fascinated.
Given an array $$$w$$$ of $$$n$$$ words, each consisting of lower-case English letters, what is the number of pairs $$$i, j$$$ such that $$$(1 \leq i \lt j \leq n)$$$ such that the words $$$w_i$$$ and $$$w_j$$$ next to each other fascinate Ahmad?
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ – the number of words in the array $$$w$$$.
The next line of each test case contains $$$n$$$ strings $$$w_1, w_2, \ldots, w_n$$$ $$$(1 \leq |w_i| \leq 13)$$$.
It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.
For each test case, print the number of fascinating pairs.
33atypical jpc ahmad4dive deep down drome4noomak noway jpc jcpcp
1 6 2
Ahmad and Monther like watching movies in the cinema, and since they go a lot (they don't), they received a special offer.
They want to watch $$$n$$$ movies, and the ticket of the $$$i$$$-th movie costs $$$a_i$$$ dinars, but they received a special offer where they can pay $$$k$$$ dinars and get $$$m$$$ special tickets that they can use to watch any movie of their liking.
Note that they can buy the offer as many times as they want, and they can have leftover tickets from the special offer at the end.
What is the minimum number of dinars they need to watch all of the movies?
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ $$$(1 \leq m \leq n \leq 2 \cdot 10^5; 1 \leq k \leq 10^9)$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$.
It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.
For each test case, print the minimum number of dinars you need to spend to watch all movies.
34 2 31 2 3 45 2 42 2 2 1 36 4 54 1 2 3 3 4
6 9 8
Later that night, Hamza, Ahmad, and Bahaa were sitting in the kitchen trying to come up with ideas to challenge each other. Hamza remembered that he had an undirected tree of $$$n$$$ nodes, and each node had an integer $$$c_i$$$ written on it.
To challenge Ahmad and Bahaa, Hamza gave them three functions:
$$$F(u, v) = $$$ The number of nodes on a simple path between nodes $$$u$$$ and $$$v$$$.
$$$G(u, v) = $$$ The greatest common divisor of each value $$$c_i$$$ where $$$i$$$ represents every node on the simple path between nodes $$$u$$$ and $$$v$$$.
$$$H(u, v) = F(u, v) \times G(u, v)$$$
And then he asked them to calculate the following summation: $$$$$$\left( \sum_{1 \leq u \lt v \leq N} H(u, v) \right) \mod 10^9 + 7$$$$$$ Can you help them find the answer?
The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of nodes in the given tree.
The second line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ $$$(1 \leq c_i \leq 10^5)$$$.
Then $$$n - 1$$$ lines follow, and each line contains two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u \lt v \leq n)$$$ indicating an edge between nodes $$$u$$$ and $$$v$$$.
It is guaranteed that these edges form a tree.
Print one integer, the summation as described in the statement.
58 1 13 26 11 21 44 34 5
54
Ahmad needed to stop gifting people an array of integers, so he decided to gift Monther a bunch of intervals this time!
Ahmad gifted Monther $$$n$$$ intervals, and he is interested in the number of ways you can choose one integer from each of the $$$n$$$ intervals such that the sum of these integers is divisible by $$$k$$$.
More formally, he is interested in the number of ways to choose $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ where ($$$l_i \leq x_i \leq r_i$$$) and their sum $$$\sum_{i=1}^{n}x_i$$$ is divisible by $$$k$$$.
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ $$$(1 \leq n \leq 2 \cdot 10^5; 1 \leq k \leq 10)$$$.
The next $$$n$$$ lines of the test case each contain two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \leq l_i \leq r \leq 10^9)$$$.
It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2\cdot 10^5$$$.
For each test case, print the number of ways you can choose an array $$$x$$$ as described above modulo $$$10^9 + 7$$$.
32 31 31 33 31 41 51 64 41 121 141 151 20
3 40 12600
We were discussing the number of teams that would qualify for the on-site contest, but we have not made a decision yet.
Although the number isn't known, Ahmad is sure that any team that robs at least $$$8$$$ distinct balloons will qualify.
Given that some team robbed $$$n$$$ distinct balloons, will they qualify?
The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10)$$$ – the number of test cases.
The next $$$t$$$ lines each contain an integer $$$n$$$ $$$(1 \leq n \leq 10)$$$ – the number of balloons robbed.
For each test case, $$$t$$$ print "YES" if the team will qualify; otherwise, print "NO". You can print "YES" or "NO" in any case, e.g., "YeS", "No" will be accepted.
45728
NO NO NO YES
Ahmad was a judge of an on-site contest where all contestants were next to each other on a line. At some point in the contest, he noticed that every contestant at that moment solved exactly one problem, meaning each contestant had balloons of only one color; what a coincidence!
There were $$$n$$$ contestants, each with a balloon of color $$$a_i$$$. Ahmad began to wonder: what is the smallest number of consecutive contestants needed to cover all the balloon colors present among the contestants?
More formally, let $$$S(b)$$$ equal the set of distinct colors in array $$$b$$$. What is the length of the smallest subarray $$$a_l, a_{l + 1}, \ldots, a_r$$$ where $$$(1 \leq l \leq r \leq n)$$$ and $$$S(a[l \ldots r]) = S(a)$$$?
The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3$$$) – the number of test cases.
The first line of each test case contains an integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$ – the number of contestants.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq n)$$$ – the balloon color of each contestant.
It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.
For each test case, print the length of the smallest subarray that contains all the distinct colors apparent in $$$a$$$.
341 2 3 452 2 2 1 364 1 2 3 3 4
4 3 4