B'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 xe2 x80 x89- xe2 x80 x891 rocks, possesses power p and we want to add the rock charged with power wk then value of power of a new tower will be {wk}p. Rocks are added from the last to the first. That is for sequence w1, xe2 x80 x89..., xe2 x80 x89wm value of power will be After 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, xe2 x80 x89l xe2 x80 x89+ xe2 x80 x891, xe2 x80 x89..., xe2 x80 x89r. First line of input contains two integers n (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105) and m (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89m xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89109). Second line of input contains n integers wk (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89wk xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89109) which is the power of rocks that priests have. Third line of input contains single integer q (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89q xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105) which is amount of queries from priests to you. kth of next q lines contains two integers lk and rk (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89lk xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89rk xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n). Output q integers. k-th of them must be the amount of cumulative power the tower will have if is built from rocks lk, xe2 x80 x89lk xe2 x80 x89+ xe2 x80 x891, xe2 x80 x89..., xe2 x80 x89rk. 327 xe2 x80 x89= xe2 x80 x897625597484987 '...