{"raw_statement":[{"iden":"statement","content":"An IT company puts out an advertisement to hire staff for a newly established office. They received n applications and organized an interview to select the best ones. They want to recruit candidates with both high level of expertise and good teamwork skill. Each candidate is assigned an ACM (Ability Coefficient of Multi-collectives) score that represents how the candidate meets the company’s internal selection criteria. Initially, everyone’s ACM score is 1.\n\nCandidates are arranged into a round table of n seats, indexed from 1 to n. The first person sits next to the second person and the nth person. For each interview question, candidates with indices from L and R form a group and register their collective answer to the system. If L ≤ R, the group consists of candidates at indices L, L + 1, L + 2, ..., R. If L > R, the group consists of candidates at indices L, L + 1, ..., N, 1, ..., R. Depending on the answer, the ACM score of each group member is either multipled by X or divided by Y (in the later case, it is guaranteed that all ACM scores of the group are divisible by Y).\n\nDuring the interview, the company may also request the system to output the product of the ACM scores of a group. This product could be a large number, so the system has to only output the value at modulo P. In summary, the system has to handle the following three types of queries:\n\nFor every query, we have 1 ≤ L, R ≤ N, 1 ≤ P ≤ 109 + 7, 1 ≤ X, Y ≤ 150.\n\nYour task is to implement the system and output the computed products for every query of type 0. \n\nThe input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 20. The following lines describe the datasets.\n\nEach dataset comes in the following format: \n\nFor each dataset, write out the corresponding outputs for queries of type 0 where each query output is on a separate line.\n\n"},{"iden":"input","content":"The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 20. The following lines describe the datasets.Each dataset comes in the following format:   The first line contains 2 integers n, m where n is the number of candidates and m is the number of queries to be processed (1 ≤ n, m ≤ 50000).  In the next m lines, the ith line contains the ith query. "},{"iden":"output","content":"For each dataset, write out the corresponding outputs for queries of type 0 where each query output is on a separate line."},{"iden":"examples","content":"Input26 50 1 5 10000000071 2 4 150 1 6 87041732 2 3 30 1 6 10000000076 61 1 4 201 2 6 150 1 6 97043312 3 6 50 1 4 10000000070 1 5 1000000007Output1337537517758802160000064800000"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of candidates.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the ACM score vector, initialized as $ a_i = 1 $ for all $ i \\in \\{1, \\dots, n\\} $.  \nLet $ P \\in \\mathbb{Z}^+ $, $ P \\leq 10^9 + 7 $, be the modulus.  \nLet $ Q $ be the number of queries.  \n\nEach query is one of three types:  \n- **Type 0 (Query)**: Given $ L, R $, compute $ \\prod_{i \\in G(L,R)} a_i \\mod P $, where $ G(L,R) $ is the circular contiguous segment from $ L $ to $ R $.  \n- **Type 1 (Update)**: Given $ L, R, X $, update $ a_i \\gets a_i \\cdot X $ for all $ i \\in G(L,R) $.  \n- **Type 2 (Update)**: Given $ L, R, Y $, update $ a_i \\gets a_i / Y $ for all $ i \\in G(L,R) $, with $ Y \\mid a_i $ for all $ i \\in G(L,R) $.  \n\n**Circular Segment Definition**  \nFor $ L, R \\in \\{1, \\dots, n\\} $:  \n$$\nG(L,R) = \n\\begin{cases}\n\\{L, L+1, \\dots, R\\} & \\text{if } L \\leq R \\\\\n\\{L, L+1, \\dots, n, 1, 2, \\dots, R\\} & \\text{if } L > R\n\\end{cases}\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq Q \\leq 10^5 $  \n3. $ 1 \\leq L, R \\leq n $  \n4. $ 1 \\leq X, Y \\leq 150 $  \n5. $ 1 \\leq P \\leq 10^9 + 7 $  \n6. For type 2 queries: $ Y \\mid a_i $ for all $ i \\in G(L,R) $  \n\n**Objective**  \nFor each query of type 0, output $ \\left( \\prod_{i \\in G(L,R)} a_i \\right) \\mod P $.","simple_statement":"You are given a circular table with n people, each starting with score 1.  \nYou need to handle 3 types of queries:  \n\n1. **0 L R P**: Output the product of scores from person L to R (circular), modulo P.  \n2. **1 L R X**: Multiply all scores from L to R (circular) by X.  \n3. **2 L R Y**: Divide all scores from L to R (circular) by Y (guaranteed to divide evenly).  \n\nIn circular range L to R:  \n- If L ≤ R: range is [L, L+1, ..., R]  \n- If L > R: range is [L, L+1, ..., n, 1, 2, ..., R]  \n\nAll operations are modulo P for output, but scores are kept as exact integers.  \nProcess multiple datasets (≤20). For each type-0 query, print the result on a new line.","has_page_source":false}