C. 01感染
time limit per test
2.5 s
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$Paranoid$$$总是以为自己写题很厉害，于是 $$$ericxie$$$ 给他出了道题。

$$$Paranoid$$$现在被给予一个只含$$$0$$$或$$$1$$$的字符串，除了第一天外，每天开始时，与$$$1$$$相邻的$$$0$$$就会变成$$$1$$$。

比如第一天开始时字符串为$$$0010001$$$，那么第二天开始时字符串就会变为$$$0111011$$$，第三天开始时就会变为$$$1111111$$$。

现在$$$Paranoid$$$要给出$$$q$$$次询问的结果，每次询问都会被给予$$$d,l,r$$$三个数字，$$$Paranoid$$$要回答出第$$$d$$$天时，$$$01$$$串从第$$$l$$$个位置到第$$$r$$$个位置范围内，有多少个字符为$$$1$$$。

注意每天询问是发生在当天的$$$01$$$转化之后的

Input

第一行一个整数 $$$T$$$，表示数据组数

每组测试数据的第一行是：第一天的$$$01$$$串$$$str$$$$$$(1 \le len(str) \le200000)$$$，查询次数$$$q(1\le q \le 200000)$$$

接下来$$$q$$$行，每行有三个整数$$$d(1\le d\le 10^9),l,r(1\le l \le r\le n)$$$，代表题目描述中的意思。

保证$$$\sum_{i=1}^{T}q_i\le 1000000,\sum_{i=1}^{T}len(str)_i\le 1000000$$$

Output

每组数据输出$$$q$$$行，代表查询的结果

Example
Input
1
0010001 3
1 1 3
2 1 3
3 1 3
Output
1
2
3