{"raw_statement":[{"iden":"statement","content":"Eugene, the number theorist, is studying some #cf_span(class=[tex-font-style-underline], body=[quirky]) integers. An integer x is #cf_span(class=[tex-font-style-underline], body=[quirky]) if there is no integer k such that k2 is a factor of x, and there is no prime number p ≥ 300 such that p divides x.\n\nEugene is playing with a sequence a1, a2, ..., an of quirky integers. Henry challenged Eugene to answer the following queries: \n\nFor example, if Eugene had the integers 6, 10, 13 and the query 1 1 3 14, he would not change 6 or 10 since their sequences of divisors ( and  respectively) are lexicographically smaller than 14's sequence , but he would change 13 to 14 since  is lexicographically larger than .\n\nThe first line contains a positive integer n (1 ≤ n ≤ 105).\n\nThe second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 107). It is guaranteed that each ai is quirky.\n\nThe third line contains a positive integer q (1 ≤ q ≤ 2·105): the number of queries. Then follow q lines, each of the form 1 l r x or 2 l r (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 107): queries of type 1 or 2, respectively. It is guaranteed that x is quirky.\n\nFor each query of type 2 l r, output  modulo 109 + 7.\n\n"},{"iden":"input","content":"The first line contains a positive integer n (1 ≤ n ≤ 105).The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 107). It is guaranteed that each ai is quirky.The third line contains a positive integer q (1 ≤ q ≤ 2·105): the number of queries. Then follow q lines, each of the form 1 l r x or 2 l r (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 107): queries of type 1 or 2, respectively. It is guaranteed that x is quirky."},{"iden":"output","content":"For each query of type 2 l r, output  modulo 109 + 7."},{"iden":"examples","content":"Input36 10 1351 1 3 142 1 12 2 22 3 32 1 3Output61014210Input1652 1 11 1 1 22 1 11 1 1 12 1 1Output621"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ \\mathcal{Q} \\subset \\mathbb{Z}^+ $ be the set of *quirky* integers:  \n$ x \\in \\mathcal{Q} $ if and only if:  \n- $ \\nexists \\, k \\in \\mathbb{Z}^+ $ such that $ k^2 \\mid x $, and  \n- $ \\nexists \\, p \\in \\mathbb{P} $ with $ p \\geq 300 $ such that $ p \\mid x $.  \n\nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of quirky integers.  \nFor any $ x \\in \\mathcal{Q} $, let $ D(x) $ denote the *sorted list of positive divisors* of $ x $, ordered increasingly.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq a_i \\leq 10^7 $ and $ a_i \\in \\mathcal{Q} $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq q \\leq 2 \\cdot 10^5 $  \n4. For each query:  \n   - Type 1: $ 1 \\; l \\; r \\; x $, where $ x \\in \\mathcal{Q} $, $ 1 \\leq l \\leq r \\leq n $  \n   - Type 2: $ 2 \\; l \\; r $, where $ 1 \\leq l \\leq r \\leq n $  \n\n**Operations**  \n- **Type 1 Query ($ 1 \\; l \\; r \\; x $)**:  \n  For each $ i \\in \\{l, \\dots, r\\} $, if $ D(x) \\succ D(a_i) $ (lexicographically), then set $ a_i \\leftarrow x $.  \n\n- **Type 2 Query ($ 2 \\; l \\; r $)**:  \n  Output $ \\left( \\sum_{i=l}^{r} a_i \\right) \\bmod (10^9 + 7) $.  \n\n**Objective**  \nProcess $ q $ queries and output the result for each type-2 query.","simple_statement":"You are given an array of \"quirky\" integers.  \nYou must handle two types of queries:  \n1. For range [l, r], replace each number with x if the list of its divisors is lexicographically smaller than x’s divisor list.  \n2. For range [l, r], count how many numbers are equal to x.  \n\nOutput the count for each type-2 query modulo 10^9+7.","has_page_source":false}