{"raw_statement":[{"iden":"statement","content":"Fouad, the ACPC judges, and organizers were hungry, so they went to a restaurant. This restaurant makes chicken cubes in seekh (skewers), such that each seekh has N chicken cubes in which the ith cube has an integer Ai that represents the mixture of spices used to cook that cube. A set of successive cubes are considered delicious from Fouad's perspective when the greatest common divisor (GCD) of their mixture of spices is exactly equal to D. \n\nSince Fouad wants to try many sub-parts of the seekh, he keeps asking the judges some queries such that each query consists of three integers L, R, and D, and he wants to know what is the number of consecutive sub-parts of the seekh in the range AL, AL + 1, ..., AR that the GCD of their mixtures of spices is equal to D; that is the count of all pairs (i, j) such that gcd(Ai, Ai + 1, ..., Aj) = D and L ≤ i ≤ j ≤ R.\n\nSince the judges want to relax and not solve problems and just eat, they asked you to solve this problem for them. Can you solve it?\n\nThe first line of the input contains a single integer T specifying the number of test cases.\n\nEach test case begins with a line containing two integers N and Q (1 ≤ N ≤ 105, 1 ≤ Q ≤ 5·104), in which N is the number of chicken cubes in a seekh, and Q is the number of queries Fouad will ask. \n\nThen a line follows containing N integers A1, ..., AN (1 ≤ Ai ≤ 106), in which Ai represents the mixture of spices used to cook the ith chicken cube.\n\nThen Q lines follow, each line contains three space-separated integers L, R, and D (1 ≤ L ≤ R ≤ N, 1 ≤ D ≤ 106), giving the queries.\n\nFor each test case, print a single line per query containing the number of consecutive sub-parts of the seekh in the given range [L, R] that the GCD of their mixtures of spices is equal to D.\n\nGreatest Common Divisors of multiple arguments is computed recursively according to the equation .\n\n"},{"iden":"input","content":"The first line of the input contains a single integer T specifying the number of test cases.Each test case begins with a line containing two integers N and Q (1 ≤ N ≤ 105, 1 ≤ Q ≤ 5·104), in which N is the number of chicken cubes in a seekh, and Q is the number of queries Fouad will ask. Then a line follows containing N integers A1, ..., AN (1 ≤ Ai ≤ 106), in which Ai represents the mixture of spices used to cook the ith chicken cube.Then Q lines follow, each line contains three space-separated integers L, R, and D (1 ≤ L ≤ R ≤ N, 1 ≤ D ≤ 106), giving the queries."},{"iden":"output","content":"For each test case, print a single line per query containing the number of consecutive sub-parts of the seekh in the given range [L, R] that the GCD of their mixtures of spices is equal to D."},{"iden":"note","content":"Greatest Common Divisors of multiple arguments is computed recursively according to the equation ."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ G = (V, E) $ be a weighted connected undirected graph, where $ V = \\{1, 2, \\dots, N\\} $, $ |E| = M $, and each edge $ e = (u, v, w) \\in E $ has weight $ w \\in \\mathbb{Z}^+ $.  \n- Let $ \\mathcal{M} $ denote the set of all minimum spanning trees (MSTs) of $ G $.  \n- Let $ S \\subseteq V^* $ be the current stack (sequence of nodes) maintained by the robot. Initially, $ S = \\emptyset $.  \n\n**Commands**  \nFor each of the $ Q $ commands:  \n- Type 1: Push node $ u $ onto $ S $: $ S \\leftarrow S \\oplus [u] $.  \n- Type 2: Validate $ S $: Check whether there exists an MST $ T^* \\in \\mathcal{M} $ such that for every pair of consecutive nodes $ (s_i, s_{i+1}) $ in $ S $, the edge $ (s_i, s_{i+1}) \\in E(T^*) $.  \n- Type 3: Pop the top node from $ S $: $ S \\leftarrow S[0:-1] $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 10 $ (implied by constraints on $ N, M, Q $)  \n2. $ 2 \\le N \\le 10^5 $, $ 1 \\le M \\le 10^5 $, $ 1 \\le Q \\le 10^5 $  \n3. For each edge: $ 1 \\le u, v \\le N $, $ u \\ne v $, $ 1 \\le w \\le 10^4 $  \n4. For each command:  \n   - Type: $ t \\in \\{1, 2, 3\\} $  \n   - If $ t = 2 $, then $ 1 \\le u \\le N $  \n\n**Objective**  \nFor each command of type 2, output:  \n- `'y'` if there exists an MST $ T^* \\in \\mathcal{M} $ such that every consecutive edge in the current sequence $ S $ is present in $ T^* $,  \n- `'n'` otherwise.","simple_statement":"You are given a weighted undirected graph with N nodes and M edges.  \nA robot has a stack of nodes. You must process Q commands:  \n\n- Type 1: Push a node u onto the stack.  \n- Type 2: Check if the current stack sequence of nodes can be part of some MST.  \n  - That is: Can you add some edges from the original graph so that the sequence forms a path in an MST?  \n  - Print 'y' if yes, 'n' if no.  \n- Type 3: Pop the top node from the stack.  \n\nFor each type-2 command, output 'y' or 'n'.","has_page_source":false}