HZNUOJ

B_M的斐波那契

Tags:
Time Limit:  2 s      Memory Limit:   256 MB
Submission:169     AC:28     Score:100.00

Description

B_M有一个长度为$n$的下标从$1$开始的数组$a$,初始时所有数均为$1$。

现在有两种操作:

    $1 \; l \; r$:把$l-r$区间内每个数加一

    $2 \; l \; r \; k$:询问$k \le \sum_{i=l}^r fib(ai)$是否成立

$fib(i)$为斐波那契数列的第$i$项,$fib(0)=0,fib(1)=1,fib(i)=fib(i-1)+fib(i-2)$

但是B_M不会做这道题,所以他把问题扔给你了

Input

第一行两个整数$n,m$($1 \le n\le 10^5,1 \le m \le 10^5$) 表示数组长度和操作次数

下面$m$行操作

为$ 1 \; l \; r$和$2 \; l \; r \; k$中的一种($1 \le l \le r \le n,1 \le k \le 10^{10}$)

Output

对于每个$2$操作,输出"YES"或者"NO"

Samples

input
5 4 2 1 4 4 2 1 3 4 1 1 2 2 1 3 4
output
YES NO NO
input
5 4 1 1 5 1 3 5 2 2 4 5 2 1 5 8
output
YES YES

Author

SUN, Zhouyi