After eating Bamboza and Salankateh at Bi Laban in Egypt , and because he really likes matrices, Ahmad invented a new type of matrix named "Matrix Bel Lotus".
A "Matrix Bel Lotus" is a square matrix $$$A$$$ with the property that for some positive integer $$$K$$$, the matrix raised to the $$$K$$$-th power equals the zero matrix, i.e., $$$A^K = 0$$$. The smallest such $$$K$$$ is called the index of lotusency. Lotus matrices always have zero as their only eigenvalue. They are important in the study of linear transformations that "collapse" vectors to zero after repeated application. Lotus matrices often appear in the Jordan normal form of matrices. They are used in solving differential equations and understanding matrix exponentials. Despite being non-invertible, they reveal structure about the linear operator they represent.
Ammar hates matrices , so he told Ahmad that all the matrices (including the Lotus one) are useless. They fought for a few hours and then decided to go and ask Mousa which is better , the life with matrices or without matrices and with any other thing.
If Mousa says "matrix" , Ahmad will be happy; otherwise, Ammar will be happy.
Can you decide who will be happy??
The first and only line contains a string $$$S \: (1 \le |S| \le 100)$$$ consisting of small Latin letters — the word Mousa will say to Ahmad and Ammar.
Print 'A' for Ahmad if the word is "matrix" and print 'A' for Ammar otherwise.
matrix
A
After learning the basics of matrices, Derar wants to learn the newest matrix algorithm "Matrix Bel Lotus."
Ahmad, its author, gave Derar $$$n$$$ videos. Video $$$i$$$ is $$$d_i$$$ minutes long.
Derar has $$$T$$$ minutes before the contest, and he has to watch all the videos. He can't skip a video, but he can watch video $$$i$$$ with any of the following speeds:
- X$$$1$$$ speed: he will need $$$d_i$$$ minutes and will get $$$100$$$ skill points.
- X$$$1.5$$$ speed: he will need $$$\frac{d_i}{1.5}$$$ minutes and will get $$$75$$$ skill points.
- X$$$2$$$ speed: he will need $$$\frac{d_i}{2}$$$ minutes and will get $$$50$$$ skill points.
It is guaranteed that $$$d_i$$$ is a multiple of $$$6$$$. So it can be proven that all the values in the problem are integers. And it is guaranteed that Derar can watch all the videos if he plays them at speed X$$$2$$$.
You have to help Derar choose the speed of each video so he can watch all the videos in at most $$$T$$$ minutes and maximize the total sum of skill points.
The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$ — the number of testcases.
The first line of each testcase consists of two integers $$$n , T \: (1 \leq n \leq 2 \cdot 10^5) (1 \leq T \leq 10^{10})$$$ — the number of videos and the number of minutes Derar has before the contest.
The second line of each testcase consists of $$$n$$$ integers $$$d_i \: (1 \leq d_i \leq 10^{10}) $$$ — the duration of each video. It is guaranteed that $$$d_i$$$ is a multiple of $$$6$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$ , and Derar can watch all the videos if he plays them at speed X$$$2$$$.
The output of each testcase consists of two lines:
On the first line, print the maximum sum of skill points Derar can achieve.
On the second line, print $$$n$$$ values, the speed he will watch each video with. The values should be $$$1 , 1.5$$$ or $$$2$$$.
If there are multiple solutions, print any.
23 186 6 63 8436 24 60
300 1 1 1 225 1.5 1 2
After studying the "Matrix Bel Lotus", Muhannad (not you, Nahhal) invented a new concept in numbers, the lotusency. The lotusency of an integer $$$Y$$$ is the number of times it can be square-rooted while still remaining an integer. For example:
- Lotusency of $$$9$$$ is $$$1$$$ because $$$9 \rightarrow 3$$$.
- Lotusency of $$$16$$$ is $$$2$$$ because $$$16 \rightarrow 4 \rightarrow 2$$$.
- Lotusency of $$$5$$$ is $$$0$$$ because its square-root is not an integer.
Muhannad has an integer $$$X$$$, and he wants to maximize its lotusency. He can do the following operation at most $$$K$$$ times:
- Choose any prime number $$$p$$$ and set $$$X = X \cdot p$$$.
What is the maximum lotusency he can obtain?
The first line contains a single integer $$$tc \: (1 \leq tc \leq 2 \cdot 10^5)$$$ — the number of testcases.
The first and only line of each testcase consists of two integers $$$X,K \: (2 \leq X \leq 2 \cdot 10^5) (0 \leq K \leq 10^{18})$$$.
For each testcase, print a single integer, the maximum lotusency Muhannad can obtain.
35 18 5200000 1000000000000000000
1 3 58
Ammar and Ahmad decided to ask Obada to moderate a debate.
Ahmad (the affirmative team) is trying to prove that his algorithm "Matrix Bel Lotus" can solve any problem.
While Ammar (the opposing team) is going against his argument, Ammar needs your help.
Ahmad has some experience in debating, so Ammar needs to keep track of his debate tree and needs to know the lowest common ancestors of some nodes to support his arguments.
There are $$$n$$$ arguments in total, and the first argument is the main argument, while each other argument is either based on the main argument or another argument.
You will be given an array $$$a$$$ of $$$n$$$ elements, each element $$$a[i]$$$ which indicates that the argument number $$$i$$$ is based on the argument number $$$a[i]$$$.
Now, of course, Ahmad (an expert in debating) will try to juggle the arguments around and try to confuse Ammar by doing some updates on the array $$$a$$$, and occasionally Ammar will ask you some questions.
- "$$$1$$$ $$$l$$$ $$$r$$$" : for every $$$l \le i \le r$$$ do $$$a[i]=max(1,a[a[i]])$$$
- "$$$2$$$ $$$l$$$ $$$r$$$ $$$x$$$" : for every $$$l \le i \le r$$$ do $$$a[i] = max(1,a[i]-x)$$$
- "$$$3$$$ $$$u$$$ $$$v$$$" : print $$$LCA(u,v)$$$
The first line contains $$$tc$$$ $$$(1 \leq tc \leq 100)$$$ — the number of test cases.
The first line of each test case contains two integers $$$n,q$$$ $$$(2 \leq n \leq 10^5)$$$ $$$(1 \leq q \leq 10^5)$$$ — the number of arguments and the number of queries.
The next line contains $$$n$$$ integers that represent the array $$$a$$$ $$$(1 \le a[i] \lt i)$$$ except for $$$a[1] = -1$$$.
The following $$$q$$$ lines will be one of the following:
- "$$$1$$$ $$$l$$$ $$$r$$$" $$$(2 \le l \le r \le n)$$$
- "$$$2$$$ $$$l$$$ $$$r$$$ $$$x$$$" $$$(2 \le l \le r \le n)$$$ $$$(1 \le x \le n-1)$$$
- "$$$3$$$ $$$u$$$ $$$v$$$" $$$(1 \le u,v \le n)$$$
It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$10^5$$$ , and the sum of $$$q$$$ over all testcases doesn't exceed $$$10^5$$$.
For each query of type $$$3$$$, print the answer.
111 5-1 1 1 2 2 3 3 4 4 5 53 8 102 7 10 23 10 61 10 113 11 5
2 3 2
Initially, the tree looks like this:
Then after the second query:
Then after the fourth query:
After the debate with Ahmad, Ammar went to B.Laban to eat his favorite Mango Bamboza. But when he went there, he found out that B.Laban has nothing other than "Matrix Bel Lotus". Very angry, he went home to play with his array $$$a$$$ of $$$n$$$ integers and his empty array $$$b$$$.
Ammar decided to do the following:
- He will choose exactly $$$k$$$ non-empty subsequences from $$$a$$$(they could intersect), calculate the mex of each subsequence, and add it to array $$$b$$$.
- He will calculate $$$X$$$, the mex of array $$$b$$$.
- He will eat $$$X$$$ Mango Bambozas from his fridge(yes, Ammar has infinite Bambozas in his fridge, but he went to B.Laban to eat fresh ones).
Now Ammar wonders what is the maximum number of Bambozas he could eat if he chooses the subsequences optimally?
The MEX(minimum excluded value) of an array is the smallest non-negative integer that is not in the array. For example:
- The MEX of $$$[2,2,1]$$$ is $$$0$$$ because it is not in the array.
- The MEX of $$$[2,2,0]$$$ is $$$1$$$ because $$$0$$$ is in the array but $$$1$$$ is not.
A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. You can erase any elements, not necessarily going successively. The remaining elements preserve their order. For example, for the array $$$[5,3,1,2,4]$$$ the following arrays are subsequences: $$$[3]$$$ , $$$[5,3,1,2,4]$$$ , $$$[5,1,4]$$$ , but the array $$$[1,3]$$$ is not.
The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$ — the number of testcases.
The first line of each testcase consists of two integers $$$n , k \: (1 \leq n \leq 3 \cdot 10^5) (1 \leq k \leq min(10^{16} , 2^n -1) )$$$ .
The second line of each testcase consists of $$$n$$$ integers $$$a_i (0 \leq a_i \leq 10^9)$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$3 \cdot 10^5$$$.
For each testcase, print a single integer, the maximum number of Bambozas Ammar could eat.
22 31 15 100 1 2 3 4
1 6
Ammar got enough and can't take those matrices stuff anymore. So he decided to go visit his wizard friend and tell him to remove the matrices from the world. So he travelled to hate-matrix land where his friend lives.
Hate-matrix land is a rooted tree of $$$n$$$ nodes; there are some rules in hate-matrix land:
- The parent of node $$$x$$$ is the unique node that is directly connected to $$$x$$$ by an edge and is closer to the root than $$$x$$$.
- Nodes $$$x$$$ and $$$y$$$ are siblings if they have the same parent.
- If a person currently is in node $$$x$$$, he can go to node $$$y$$$ if and only if $$$y$$$ is the parent of $$$x$$$ or $$$x$$$ and $$$y$$$ are siblings.
In the tree in the photo, $$$1$$$ is the parent of $$$2$$$ , and $$$2$$$ and $$$4$$$ are siblings. If you start in node $$$3$$$, you can go to node $$$2$$$ because it is its parent, and then you can go to node $$$4$$$ because $$$2$$$ and $$$4$$$ are siblings. So node $$$4$$$ is reachable by $$$3$$$, but $$$5$$$ isn't.
Ammar knows that the tree is rooted at node $$$root$$$; he currently is in node $$$x$$$, and his friend is in node $$$y$$$. They want to meet in either $$$x$$$ (his friend must be able to reach it) or in node $$$y$$$(he has to be able to reach it). Can you help Ammar find out whether they could meet and remove matrices forever? You have to answer $$$q$$$ queries.
The first line contains two integers $$$n,q \: (2 \leq n \leq 2 \cdot 10^5)(1 \leq q \leq 2 \cdot 10^5)$$$ —the number of nodes and the number of queries.
Each of the next $$$n-1$$$ lines consists of two integers $$$u,v \: (1 \leq u,v \leq n)$$$ — the description of the edges of the tree. It's guaranteed that the given edges form a valid tree.
Each of the next $$$q$$$ lines consists of three integers $$$root,x,y \: (1 \leq root,x,y \leq n)$$$ — the description of each query.
For each query, print "YES" if they could meet and "NO" otherwise.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
5 51 22 31 44 51 2 41 3 54 5 32 2 33 1 5
YES NO YES YES YES
Even after removing matrices forever, Ammar was still angry and asked the wizard to throw Ahmad in a new maze.
The maze this time is an infinite coordinates system with some cells containing walls and others empty. A cell $$$(x,y)$$$ is a block that Ahmad can't go to if $$$max(|x|,|y|)$$$ is odd.
You could notice that blocks will be in a shape of layers , so every layer has four walls : top, bottom, left, and right , and the center of the layers is an empty cell with coordinates $$$(0,0)$$$.
A wall can have at most one special block that Ahmad can use to go only from the inside of the layer to the outside; there are $$$m$$$ special blocks in the maze. Ahmad knows that only the first $$$n$$$ layers could contain special blocks, and the $$$n+1_{th}$$$ layer is always a complete wall.
In the image, $$$n=3$$$ and $$$m=4$$$. And the coordinates of the special blocks are $$$(-1,0) , (0,-1) , (3,-1)$$$ and $$$(-3,2)$$$.
As you know, Ahmad loves matrices. Ahmad is currently in cell $$$(S_x,S_y)$$$ and there is a matrix problem in cell $$$(G_x,G_y)$$$ , where both $$$S$$$ and $$$G$$$ are empty points. If Ahmad is currently in a cell, he could move up, down, left, or right and only into an empty cell or a special block(if he is inside the layer and going outside ). In other words, if he is in cell $$$(x,y)$$$ , he can move to $$$(x-1,y) , (x+1,y) , (x,y-1)$$$ or $$$(x,y+1)$$$.
Ahmad asks you to tell him what is the minimum path length that he could take to reach the matrix problem. You have to answer $$$q$$$ queries!
The first line contains three integers $$$n,m,q \: (1 \leq n,q \leq 10^5) (0 \leq m \leq 4 \cdot n)$$$ — the number of layers , the number of special blocks, and the number of queries.
Each of the next $$$m$$$ lines contains two integers $$$x,y \: (-2 \cdot n \leq x,y \leq 2 \cdot n)$$$ — the coordinates of the special blocks. It is guaranteed that all the special points are block cells ($$$max(|x|,|y|)$$$ is odd), $$$|x| \neq |y|$$$, and each wall contains at most one special block.
Each of the next $$$q$$$ lines contains 4 integers: $$$S_x, S_y, G_x, G_y \: (-2 \cdot n \leq S_x,S_y,G_x,G_y \leq 2 \cdot n)$$$ — Ahmad's current position and the matrix problem position. It is guaranteed that $$$max(|S_x|,|S_y|)$$$ and $$$max(|G_x|,|G_y|)$$$ are even (they are empty cells).
For each query, print the minimum length of a path that Ahmad could take to get to the matrix problem, or -1 if he can never reach it.
3 4 7-1 00 -13 -1-3 20 0 4 4-2 0 0 0-2 0 4 42 2 -4 -4-4 -4 4 44 4 6 6-6 0 6 0
12 -1 14 12 16 -1 24
When Ahmad found out about Ammar's evil plan, he got mad and decided to take revenge. He asked his wizard friend Mousa (yes, everyone has a wizard friend) to help him.
Mousa threw Ammar in a DAG (directed acyclic graph) of $$$n$$$ nodes and $$$m$$$ edges, where each edge has a lowercase letter on it , and to escape he has to find the password. The password is a string $$$s$$$ of length $$$k$$$ , consisting of lowercase letters. Ammar starts in node $$$1$$$ and will choose a path to take in the graph. His memory can be represented as a string $$$t$$$, initially empty. When he walks on an edge, he adds the letter on the edge to the end of $$$t$$$. But Mousa cast the forgetting spell on Ammar, so when his memory becomes equal to the password, it becomes empty again.
Ammar's memory has to be equal to a prefix (possibly empty) of the password when he finishes walking to be able to escape the DAG.
Ammar wonders how many paths of length at least $$$1$$$ in the graph he can choose so that he escapes the DAG in the end? Since the answer might be very large, print it modulo $$$10^9 + 7$$$.
The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$— the number of testcases.
The first line of each testcase consists of $$$3$$$ integers $$$n,m,k \: (2 \leq n \leq 10^5)(1 \leq m \leq 2*10^5)(1 \leq k \leq 100)$$$ —the number of nodes, the number of edges and the length of the password and when Ammar forgets everything again.
The second line of each test case contains the string $$$s$$$ of length $$$k$$$ containing only lowercase latin letters.
Each of the next $$$m$$$ lines consists of $$$2$$$ integers $$$u,v \: (1 \leq u,v \leq n) (u\not=v)$$$ and a lowercase latin letter $$$c$$$ — this means there is an edge from $$$u$$$ to $$$v$$$ with the letter $$$c$$$ on it.
Multiple edges with the same character can exist.
It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$10^5$$$.
It is guaranteed that the sum of $$$m$$$ over all testcases doesn't exceed $$$2*10^5$$$.
It is guaranteed that the sum of $$$k$$$ over all testcases doesn't exceed $$$100$$$.
For each testcase, print the number of paths Ammar can choose in order to escape the DAG, modulo $$$10^9 + 7$$$.
15 10 3cca3 4 c2 3 c3 4 a1 2 c1 2 b3 4 b2 3 b4 5 c4 5 a1 2 a
4
Ammar returned home after escaping the DAG. But unfortunately, there was no electricity.
Ammar has $$$n$$$ bulbs in his house, each one has a button that changes the state of the bulb when pressed(it turns it on if it was off and vice versa). He remembers that at most $$$k$$$ of them were on when he left, but he doesn't remember which ones (yes, Mousa's spell is still working). Ammar wants to press some buttons so that he can make sure at least one bulb is on when the electricity is back; help him find the minimum number of buttons he has to press or tell him he can never make sure at least one bulb is on otherwise.
The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$ — the number of testcases.
The only line of each testcase consists of two integers $$$n,k \: (1 \leq n \leq 2000) (0 \leq k \leq n)$$$ — the number of bulbs and the maximum number of bulbs that were on.
For each testcase, print a single integer which is the minimum number of buttons he has to press or $$$-1$$$ if he can't make sure at least one bulb is on when the electricity is back.
21 09 4
1 5
Abode the wizard (Ammar's friend who lives in Hate-matrix land) is on vacation. He found an infinite street that has $$$n$$$ trees , tree $$$i$$$ is $$$a_i$$$ meters away from the beginning of the street, and all the trees are $$$h$$$ meters tall.
Abode started walking from the beginning of the street. When he passes near a tree, he does nothing if it is already fallen. Otherwise, he casts a spell and one of the following events happens, all in equal probability:
- The tree will fall to the left
- The tree will fall to the right
- The tree will remain standing
When a tree in position $$$x$$$ falls to the right, all standing trees in positions $$$[x,x+h]$$$ will fall to the right. Similarly, if it fell to the left, all standing trees in positions $$$[x-h,x]$$$ will fall to the left.
Now Abode wonders, what is the expected value of the sum of heights of the standing trees after he passes near all the trees? Print it Modulo $$$10^9+7$$$.
Formally, let $$$M=10^9+7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q\not\equiv 0(mod M)$$$. Output the integer equal to $$$p \cdot q^{-1} mod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \leq x \lt M$$$ and $$$x \cdot q \equiv p (mod M)$$$.
The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$ — the number of testcases.
The first line of each testcase consists of two integers $$$n,h \: (1 \leq n \leq 2 \cdot 10^5) (1 \leq h \leq 10^9)$$$— the number of trees and their height.
The second line of each testcase consists of $$$n$$$ integers $$$a_i \: (1 \leq a_i \leq 10^9) (a_i \lt a_{i+1})$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.
For each testcase, print the expected value of the sum of heights of standing trees modulo $$$10^9+7$$$.
32 101 1012 101 25 101 3 4 5 25
666666678 444444452 716049396
If you know Obada, then you know how much he loves his friends. Obada was not happy because of all the problems between Ammar and Ahmad and decided to invite them to a party and solve all the problems so they become friends again. Obada invited $$$k$$$ people in total.
Obada and his friends are programmers, and programmers don't eat cake at parties; they eat arrays. Obada made a delicious array $$$a$$$ of $$$n$$$ integers. He wants to divide it into exactly $$$k$$$ non-empty subarrays such that each element of $$$a$$$ is in exactly one subarray , and give each subarray to one of his friends. Obada wants the friends to be happy, so he wants to maximize the sum of happiness of the friends. If a friend got the subarray $$$L,R$$$, then his happiness will be equal to the maximum $$$a[w] \oplus a[x] \oplus a[y] \oplus a[z]$$$ over all $$$(L \leq w, x, y, z \leq R)$$$, where $$$\oplus$$$ is the xor binary operation. Note that $$$w,x,y,z$$$ don't have to be distinct.
Can you help Obada find the maximum possible sum of happiness?
The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$— the number of testcases.
The first line of each testcase consists of two integers $$$n,k \: (1 \leq k \leq n \leq 500)$$$ —the size of the array and the number of friends.
The second line of each testcase contains $$$n$$$ integers $$$a_i \: (0 \leq a_i \leq 10^9)$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$500$$$.
For each testcase, print the maximum possible sum of happiness.
13 31 1 1
0
15 31 2 3 4 5
10
This is an interactive problem. Please read the Interaction section carefully.
After he resolved the conflict with Ahmad, Ammar went home and decided to create an interactive problem to add to this problemset. After a lot of thinking, Ammar decided to take a break so he could eat cookies and chat with his friends in their group "Richard Fan Club".
Ammar has $$$n \: (1 \leq n \leq 10^4)$$$ cookies, cookie $$$i$$$ is a circle with diameter $$$a_i \: (1 \leq a_i \leq 10^6)$$$. When Ammar eats a cookie, his happiness increases by its area. Ammar told his friends about the cookies he ate and his happiness. Later that night, Jamal (camel) opened the chat and started asking Ammar about the cookies, so Ammar decided to play the following game with him:
- Jamal will ask Ammar the following question "$$$?$$$ $$$x$$$".
- Ammar will respond with the number of cookies he ate that have two points on its circumference where the distance between them is exactly $$$x$$$.
Jamal has to find the value of Ammar's happiness after he ate all the cookies; can you help him ??
It can be proven that the happiness can be written as $$$\frac{Y \cdot \pi}{4}$$$ where $$$Y$$$ is an integer. You are asked to find $$$Y$$$.
The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$ — the number of testcases. The description of the testcases follows.
It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$10^4$$$.
The first line of each testcase contains a single integer $$$n$$$. At this moment, the array $$$a$$$ is chosen. The interactor in this task is not adaptive. In other words, the array $$$a$$$ is fixed in every testcase and does not change during the interaction.
To ask a query, print the line of the following form (without quotes):
"$$$?$$$ $$$x$$$" $$$(1 \leq x \leq 10^9)$$$.
You can ask at most $$$21 \cdot n$$$ queries of this form.
If your query is not valid or you asked more than $$$21 \cdot n $$$ queries, the interactor will respond with $$$-1$$$. If this happens, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.
After that, you receive an integer — Ammar's response to the query.
Next, if your program found Ammar's happiness, print a line with the following format(without quotes):
"$$$!$$$ $$$Y$$$"
Please read the statement to understand what $$$Y$$$ stands for.
Note that this line is not considered a query and is not taken into account when counting the number of queries asked.
The interactor will respond with $$$1$$$ if your answer is correct. Otherwise, it will respond with $$$0$$$. If this happens, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.
After this, proceed to the next testcase.
If the interactor responded to a query with $$$-1$$$ or to the guess with $$$0$$$, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.
After printing a query, do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in $$$c++$$$.
- System.out.flush() in Java
- stdout.flush() in Python
2 5 5 4 3 0 1 2 0 1
? 1 ? 3 ? 4 ? 5 ! 58 ? 2 ! 2
In the first testcase, $$$a=[1,3,4,4,4]$$$.
In the second testcase, $$$a=[1,1]$$$.
While Obada was tidying up his house for the party, he found a word written by lowercase letters balloons. Obada loves palindromes, so he wants to make the word a palindrome. Obada can only reshuffle letters of a subarray $$$[L,R]$$$ of a string. But every now and then, Obada's brother changes a letter in the string. Obada found this an interesting problem and wants you to solve it.
Obada will give you a string $$$s$$$ of $$$n$$$ lowercase letters and $$$q$$$ queries of the following types:
- "$$$1$$$ $$$i$$$ $$$c$$$" — set $$$s_i=c$$$.
- "$$$2$$$ $$$L$$$ $$$R$$$" — Obada wonders how many different palindromic strings of length $$$n$$$ he could obtain from $$$s$$$ by reshuffling the letters in the subarray $$$[L,R]$$$. In other words, the number of different palindromic strings $$$s$$$ could become equal to by reshuffling those letters. Note that this type of query doesn't really change $$$s$$$. Since the answer might be very large, print it modulo $$$10^9+7$$$.
A palindrome is a string that reads the same backward as forward; for example, strings "z", "aaa", "aba", "abccba" are palindromes, but strings "ammar", "bassam", "ab" are not.
Can you solve this problem?
The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$ — the number of testcases.
The first line of each testcase consists of two integers $$$n,q \: (1 \leq n,q \leq 10^5)$$$— the length of $$$s$$$ and the number of queries.
The second line of each test case contains the string $$$s$$$ of length $$$n$$$ containing only lowercase latin letters.
The next $$$q$$$ lines describe the queries, each line is like one of the following:
- "$$$1$$$ $$$i$$$ $$$c$$$" $$$(1 \leq i \leq n)$$$ and $$$c$$$ is a lowercase latin letter.
- "$$$2$$$ $$$L$$$ $$$R$$$" $$$(1 \leq L \leq R \leq n)$$$.
It is guaranteed that there will be at least one query of the second type in each testcase, and the sum of each of $$$n$$$ and $$$q$$$ over all testcases doesn't exceed $$$10^5$$$.
For each query of the second type, print the number of different palindromic strings he could obtain from $$$s$$$ by reshuffling the letters in the subarray $$$[L,R]$$$, modulo $$$10^9+7$$$.
410 3abcdecedba2 6 81 10 b2 6 810 5abcdeabcde2 1 102 1 51 1 e1 2 d2 3 83 4aab2 1 22 2 31 1 b2 2 35 3caabc2 2 41 5 a2 2 4
1 0 120 1 0 0 1 1 1 0
At Obada's party, Anas asked Abode to teach him some magic spells, so he taught him the well-known "A-to-B-Kedavra" spell, which is used to exchange elements between arrays. Because Anas is new to the magic world, he couldn't perfectly cast it. Anas has two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. He can use the spell as follows:
- Anas chooses an integer $$$i \: (1 \leq i \leq n)$$$ and a positive even integer $$$X \: (2 \leq X \leq a_i)$$$ and sets $$$a_i=a_i-X$$$.
- He chooses an integer $$$j \: (1 \leq j \leq n)$$$ and sets $$$b_j=b_j+\frac{X}{2}$$$.
To test Anas's skills, Abode gave him a third array $$$c$$$ of length $$$n$$$ and asked him whether he could cast multiple (possibly zero) spells to make all three arrays equal ($$$a=b=c$$$). Can you help Anas??
The first line contains a single integer $$$tc :\ (1 \leq tc \leq 100)$$$ — the number of testcases.
The first line of each testcase contains a single integer $$$n \: (1 \leq n \leq 2 \cdot 10^5)$$$.
The second line of each testcase consists of $$$n$$$ integers $$$a_i \: (1 \leq a_i \leq 10^9)$$$.
The third line of each testcase consists of $$$n$$$ integers $$$b_i \: (1 \leq b_i \leq 10^9)$$$.
The fourth line of each testcase consists of $$$n$$$ integers $$$c_i \: (1 \leq c_i \leq 10^9)$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.
For each testcase print "YES" if Anas could pass Abode's test, and "NO" otherwise.
332 6 42 3 42 4 432 5 42 3 42 4 432 6 42 4 32 4 4
YES NO YES
In the first test case, Anas could choose $$$i=2$$$, $$$X=2$$$, and $$$j=2$$$.