题目描述

小红有一个长度为 n 的数组 a ，她每次会询问区间 [l,r] 中所有数字拼接起来是否是 3 的倍数。

输入描述

第一行输入两个整数 n, q(1 <= n, q <= 105) 表示数组长度和询问次数。

第二行输入 n 个整数表示数组 a(1 <= ai <= 109) 。

接下来的q行，每行输入2个整数，表示询问的 [l, r] 区间。1 <= l <= r <= n

注意：数组的下标从1开始。

输出描述

对于每个询问输出一行，若区间所有数字拼接起来是 3 的倍数，则输出 YES，否则输出NO 。

输入示例

3 2
11 45 14
1 3
2 2

输出示例

NO
YES

提示信息

将[1, 3]拼接后，数字为114514，不是3的倍数，输出NO。将[2, 2]拼接后，数字为45，是3的倍数，输出YES。

时间限制：c/c++：1s；其他语言：3s。最后一个用例过不去可尝试使用快读。