{"raw_statement":[{"iden":"statement","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_."},{"iden":"input","content":"First 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_)."},{"iden":"output","content":"Output _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_."},{"iden":"example","content":"Input\n\n6 1000000000\n1 2 2 3 3 3\n8\n1 1\n1 6\n2 2\n2 3\n2 4\n4 4\n4 5\n4 6\n\nOutput\n\n1\n1\n2\n4\n256\n3\n27\n597484987"},{"iden":"note","content":"327 = 7625597484987"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}