{"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":"CF904F"},"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"}],"meta":{"iden":"CF904F","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"}}