描述

给出一个长为\(n\)的数列，以及\(n\)个操作，操作涉及区间加法，询问区间内小于某个值\(x\)的元素个数。

格式

输入格式

第一行输入一个数字\(n\)。

第二行输入\(n\)个数字，第\(i\)个数字为\(a_i\)，以空格隔开。

接下来输入\(n\)行询问，每行输入四个数字\(opt、l、r、c\)，以空格隔开。

若\(opt=0\)，表示将位于\([l,r]\)的之间的数字都加\(c\)。

若\(opt=1\)，表示询问\([l,r]\)中，小于\(c^2\)的数字的个数。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例1

输入样例1

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

输出样例1

3
0
2

限制

对于\(100\%\)的数据，\(1≤n≤50000,-2^{31}≤others、ans≤2^{31}-1\)。