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\)，保证数据正确