Description

众所周知，w教授是热爱科学的好少年，他一刻不刷题就会十分难受。并且每一道题带给他的愉悦度是不同的，例如有些题太简单，愉悦度就为$0$，而有些题愉悦度就很高。w教授认为，一段闭区间$[l,r]$内所有题的愉悦度是其中所有题目愉悦度的乘积。

w教授的时间十分宝贵，现在他给出一个长为$n$的题单和每道题的愉悦度，并做$m$个询问$[l,r]$，表示询问这段区间内所有题的愉悦度。由于愉悦度可能很大，你只需要输出答案对$12345678$取模的结果即可。

Input

• 第一行输入两个整数$n,m$
• 接下来一行$n$个非负整数表示每道题的愉悦度
• 接下来$m$行每行两个整数$[l,r]$，表示询问这个区间内所有题目的愉悦度，如果$l> r$，则认为询问的区间是$[r, l]$

Output

• $m$行，对于每个询问输出一行，表示所求愉悦度对$12345678$取模的结果。

Sample

Input

5 5
1 0 2 4 3
1 3
2 2
4 4
3 5
4 5

Output

0
0
4
24
12

Hint

• 对于30%的数据，$n,m\le 1000$
• 对于60%的数据，$n,m\le 20000$
• 对于100%的数据，$n,m\le 100000$，保证数据正确