{"raw_statement":[{"iden":"statement","content":"You are given an array a consisting of n elements, and q queries. There are two types of queries, as follow:\n\nA zero array is defined as an array which all its elements are zeros. There is only one allowed operation to convert an array to a zero array. At each operation, you can choose a value x and subtract it from all non-zero elements in the array, such that no element will be negative after the operation.\n\nThe first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.\n\nThe first line of each test case consists of two integers n and q (1 ≤ n, q ≤ 105), in which n is the size of the array a, and q is the number of queries. \n\nThen a line follows containing n elements a1, a2, ..., an (0 ≤ ai ≤ 109), giving the array a.\n\nThen q lines follow, each line containing a query in the format described in the problem statement. It is guaranteed that the following constraints hold for the first type of queries: 1 ≤ p ≤ n, 0 ≤ v ≤ 109.\n\nThe sum of n and q overall test cases does not exceed 106 for each.\n\nFor each query of the second type, print the minimum number of required operations to convert array a to a zero array. The queries must be answered in the order given in the input.\n\n"},{"iden":"input","content":"The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.The first line of each test case consists of two integers n and q (1 ≤ n, q ≤ 105), in which n is the size of the array a, and q is the number of queries. Then a line follows containing n elements a1, a2, ..., an (0 ≤ ai ≤ 109), giving the array a.Then q lines follow, each line containing a query in the format described in the problem statement. It is guaranteed that the following constraints hold for the first type of queries: 1 ≤ p ≤ n, 0 ≤ v ≤ 109.The sum of n and q overall test cases does not exceed 106 for each."},{"iden":"output","content":"For each query of the second type, print the minimum number of required operations to convert array a to a zero array. The queries must be answered in the order given in the input."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the width of a $ 3 \\times n $ grid.  \nLet $ a_n $ denote the number of distinct ways to tile the grid using $ 1 \\times 2 $ dominoes.\n\n**Constraints**  \n$ 1 \\leq n \\leq 10^7 $\n\n**Objective**  \nCompute $ a_n \\mod (10^9 + 7) $, where $ a_n $ satisfies the recurrence:  \n$$\na_1 = 0, \\quad a_2 = 3, \\quad a_n = 4a_{n-2} - a_{n-4} \\quad \\text{for } n \\geq 4\n$$  \nwith $ a_n = 0 $ for odd $ n $, and $ a_n $ defined only for even $ n \\geq 2 $.","simple_statement":"Count the number of ways to tile a 3×n grid using 1×2 dominoes, modulo 10^9 + 7.","has_page_source":false}