{"problem":{"name":"F. Power Tower","description":{"content":"Priests of the Quetzalcoatl cult want to build a tower to represent a power of their god. Tower is usually made of power-charged rocks. It is built with the help of rare magic by levitating the curren","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF907F"},"statements":[{"statement_type":"Markdown","content":"Priests of the Quetzalcoatl cult want to build a tower to represent a power of their god. Tower is usually made of power-charged rocks. It is built with the help of rare magic by levitating the current top of tower and adding rocks at its bottom. If top, which is built from _k_ - 1 rocks, possesses power _p_ and we want to add the rock charged with power _w__k_ then value of power of a new tower will be {_w__k_}_p_.\n\nRocks are added from the last to the first. That is for sequence _w_1, ..., _w__m_ value of power will be\n\nAfter tower is built, its power may be extremely large. But still priests want to get some information about it, namely they want to know a number called cumulative power which is the true value of power taken modulo _m_. Priests have _n_ rocks numbered from 1 to _n_. They ask you to calculate which value of cumulative power will the tower possess if they will build it from rocks numbered _l_, _l_ + 1, ..., _r_.\n\n## Input\n\nFirst line of input contains two integers _n_ (1 ≤ _n_ ≤ 105) and _m_ (1 ≤ _m_ ≤ 109).\n\nSecond line of input contains _n_ integers _w__k_ (1 ≤ _w__k_ ≤ 109) which is the power of rocks that priests have.\n\nThird line of input contains single integer _q_ (1 ≤ _q_ ≤ 105) which is amount of queries from priests to you.\n\n_k__th_ of next _q_ lines contains two integers _l__k_ and _r__k_ (1 ≤ _l__k_ ≤ _r__k_ ≤ _n_).\n\n## Output\n\nOutput _q_ integers. _k_\\-th of them must be the amount of cumulative power the tower will have if is built from rocks _l__k_, _l__k_ + 1, ..., _r__k_.\n\n[samples]\n\n## Note\n\n327 = 7625597484987","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"夸察尔科特尔教派的祭司们希望建造一座塔，以代表他们神祇的力量。塔通常由充满能量的岩石建造，通过一种稀有魔法构建：将当前塔顶悬浮，并在底部添加岩石。如果当前塔顶由 #cf_span[k - 1] 块岩石构成，其能量为 #cf_span[p]，而我们希望添加一块能量为 #cf_span[wk] 的岩石，则新塔的能量值为 #cf_span[{wk}p]。\n\n岩石的添加顺序是从最后一块到第一块。因此，对于序列 #cf_span[w1, ..., wm]，其能量值为\n\n塔建成后，其能量可能极大。但祭司们仍希望获得一些关于它的信息，具体来说，他们想知道一个称为“累积能量”的数值，即能量对 #cf_span[m] 取模后的真值。祭司们拥有 #cf_span[n] 块岩石，编号从 #cf_span[1] 到 #cf_span[n]。他们要求你计算：如果使用编号为 #cf_span[l, l + 1, ..., r] 的岩石建造塔，塔将具有多少累积能量。\n\n输入的第一行包含两个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) 和 #cf_span[m] (#cf_span[1 ≤ m ≤ 109])。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[wk] (#cf_span[1 ≤ wk ≤ 109])，表示祭司们拥有的岩石的能量。\n\n第三行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105])，表示祭司向你提出的查询数量。\n\n接下来的 #cf_span[q] 行中，第 #cf_span[k] 行包含两个整数 #cf_span[lk] 和 #cf_span[rk] (#cf_span[1 ≤ lk ≤ rk ≤ n])。\n\n请输出 #cf_span[q] 个整数。第 #cf_span[k] 个整数应为使用岩石 #cf_span[lk, lk + 1, ..., rk] 建造塔时的累积能量值。\n\n#cf_span[327 = 7625597484987]\n\n## Input\n\n输入的第一行包含两个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) 和 #cf_span[m] (#cf_span[1 ≤ m ≤ 109])。第二行包含 #cf_span[n] 个整数 #cf_span[wk] (#cf_span[1 ≤ wk ≤ 109])，表示祭司们拥有的岩石的能量。第三行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105])，表示祭司向你提出的查询数量。第 #cf_span[k] 行包含两个整数 #cf_span[lk] 和 #cf_span[rk] (#cf_span[1 ≤ lk ≤ rk ≤ n])。\n\n## Output\n\n请输出 #cf_span[q] 个整数。第 #cf_span[k] 个整数应为使用岩石 #cf_span[lk, lk + 1, ..., rk] 建造塔时的累积能量值。\n\n[samples]\n\n## Note\n\n#cf_span[327 = 7625597484987]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $, with $ 1 \\leq n \\leq 10^5 $, $ 1 \\leq m \\leq 10^9 $.  \nLet $ W = (w_1, w_2, \\dots, w_n) $ be a sequence of integers, where $ 1 \\leq w_k \\leq 10^9 $.  \n\nFor a subsequence $ W[l:r] = (w_l, w_{l+1}, \\dots, w_r) $, the **tower power** is defined recursively as:  \n$$\nP(l, r) = \n\\begin{cases}\nw_r & \\text{if } l = r \\\\\nw_l^{P(l+1, r)} \\mod m & \\text{if } l < r\n\\end{cases}\n$$  \n*(Note: Exponentiation is right-associative: $ w_l^{w_{l+1}^{\\cdot^{\\cdot^{\\cdot^{w_r}}}}} $)*\n\n**Constraints**  \n1. $ 1 \\leq q \\leq 10^5 $  \n2. For each query $ k \\in \\{1, \\dots, q\\} $: $ 1 \\leq l_k \\leq r_k \\leq n $\n\n**Objective**  \nFor each query $ (l_k, r_k) $, compute:  \n$$\nP(l_k, r_k) = w_{l_k}^{w_{l_k+1}^{\\cdot^{\\cdot^{\\cdot^{w_{r_k}}}}}} \\mod m\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF907F","tags":["math","number theory"],"sample_group":[["6 1000000000\n1 2 2 3 3 3\n8\n1 1\n1 6\n2 2\n2 3\n2 4\n4 4\n4 5\n4 6","1\n1\n2\n4\n256\n3\n27\n597484987"]],"created_at":"2026-03-03 11:00:39"}}