問題文
高桥先生喜欢创建数字序列并对它们执行各种操作。我特别喜欢对区间进行各种运算,比如计算区间之和、区间最大公约数。
因此,高桥先生认为对于某个数列,区间的最大公约数是某个值。 我决定计算 x 的间隔数。 高桥用一个程序来解决这个问题,但他意识到数字序列越长,花费的时间就越多。
你的工作是为 Takahashi 编写一个程序,即使数字序列很长也能快速运行。 此外,作为奖励功能,同一数字序列会显示多个数字。 即使有 x 候选人,所有 我决定添加一个查询功能,以便我可以计算 x 。
你有长度 给出了 n 序列 有 A=\{a_1,a_2,..,a_n\} 。另外,查询数量 m 和 还给出了 x_1,x_2,..,x_m 。 每个 对于 x_i (1 ≦ i ≦ m) ,区间中包含的所有数字的最大公约数为 一个区间使得 x_i 请输出 [s,t] (1 ≦ s ≦ t ≦ n) 的编号。
例如,A=\{1,2,4\} ,最大公约数为1的区间为[1,1],[1,2],[1,3]最大公约数为 2 的区间为[2,2],[2,3] 最大公约数为 4 的区间为 仅[3,3] 。
入力
输入将以以下格式从标准输入给出。
n m a_1 a_2 : a_n x_1 x_2 : x_m
- 1 行包含一个表示序列长度的整数。 n (1 ≦ n ≦ 100,000) 及查询次数 在 m (1 ≦ m ≦ 100,000) 用空格分隔。
- 2 从行 n 行中,序列 给出了值 A。其中 i 行中的编号规则 代表每个 A 的 已知 i 值的整数 a_i (1 ≦ a_i ≦ 10^9) 给出。
- n+2 从行 m 行给出您要检查的值。其中 行 i 在第 i 个查询中 代表 x 每个值的整数 x_i (1 ≦ x_i ≦ 10^9) 给出。
出力
从第一行开始按顺序回答每个问题。 输出 m 行。还在输出末尾添加换行符。
入力例1
3 4 1 2 4 1 2 3 4
出力例1
3 2 0 1
给出的数字序列来自问题文本。
入力例2
6 7 12 6 4 3 2 1 1 2 3 4 6 12 8
出力例2
13 3 1 1 2 1 0
入力例3
5 8 4 6 42 28 41 1 2 4 6 7 14 14 41
出力例3
4 4 1 2 0 1 1 1