HDU 6155 Subsequence Count 线段树维护矩阵DP转移

http://acm.hdu.edu.cn/showproblem.php?pid=6155

给一个01序列,有区间反转操作,询问区间内本质不同的子序列的个数 $%10^9+7$

写出dp转移方程,用$dp[i][j]$表从起点到第$i$个点,最后一位是$j$的方案数。

当第$i$位是$0$的时候:

$$dp[i][0] = dp[i-1][0] + dp[i-1][1] + 1$$

$$dp[i][1] = dp[i-1][1] $$

当第$i$位是$1$的时候:

$$dp[i][0] = dp[i-1][0] $$

$$dp[i][1] = dp[i-1][0] + dp[i-1][1] + 1$$

写成矩阵的形式进行转移

如果这一位是$0$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

如果这一位是$1$

$$\begin{bmatrix} dp[i+1][0]\\ dp[i+1][1]\\1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}\begin{bmatrix} dp[i][0]\\ dp[i][1]\\1 \end{bmatrix}$$

可以用线段树维护任意区间内的转移方程。

考虑反转,会发现把$0$矩阵交换$r_1,r_2$和$c_1,c_2$就能变成$1$矩阵,反之亦然。令$T=\begin{bmatrix} 0 & 1& 0\\ 1 & 0 &0\\0 & 0 & 1 \end{bmatrix}$,可知$TT=E$

交换行,可以在矩阵前乘以个 $T$,交换列,可以在矩阵后乘以一个$T$。假设$C=AB$ ,那么$TCT = TABT = TATTBT$。意味着,进行区间反转的时候,将维护的转移矩阵进行交换行列就好了,并打上延时标记。

 

HDU 6153 A Secret KMP计数

http://acm.hdu.edu.cn/showproblem.php?pid=6153

给定两个串$s_1$,$s_2$,求$s_2$的每一个后缀在$s_1$中出现的次数$\times$长度的和。

将$s_1$,$s_2$进行反转,就变成了求$s_2$的每一个前缀在$s_1$中出现的次数$\times$长度的和。处理出$s_2$的next数组,用$s_2$对$s_1$进行匹配,假设$s_2[j]$和$s_1[i]$匹配上了,那么新出现的前缀就有$s_2[j],s_2[next[j]],s_2[next[next[j]],……$。但是并不能在匹配的过程中进行next跳转计数,会超时的。可以记录每个匹配长度值出现的次数,那么如果前缀$j$出现过,那么前缀$next[j]$也一定出现过。匹配完后,cnt[next[j]] += cnt[j]即可算出每个前缀出现的次数。

HDU 6053 TrickGCD 容斥 DFS 分段快速查询

http://acm.hdu.edu.cn/showproblem.php?pid=6053

TrickGCD

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

You are given an array $A$ , and Zhu wants to know there are how many different array $B$ satisfy the following conditions?
* $1\leq B_{i} \leq A_{i}$
* For each pair( l , r ) ($1 \leq l \leq r \leq n$) , $gcd( b_{l} , b_{l+1} ... b_{r} )\ge 2$

Input

The first line is an integer T($1 \leq T \leq 10$) describe the number of test cases.
Each test case begins with an integer number n describe the size of array $A$.
Then a line contains $n$ numbers describe each element of $A$
You can assume that $1 \leq n , A_{i} \leq 10^5$

Output

For the $k$th test case , first output "Case #k: " , then output an integer as answer in a single line . because the answer may be large , so you are only need to output answer $mod$ $10^9+7$

Sample Input

1
4
4 4 4 4

Sample Output

Case #1: 17

Source

题意

给定一个$A_i$数组,构造一个$B_i$数组,满足 $1\leq B_{i} \leq A_{i}$,且$B_i$数组的最大公约数不为1

思路

先将$A_i$排序,使用dfs枚举是否使用每一个质因子,容斥计算$B_i$数组的每一个数是dfs枚举的数的积的倍数。对于每次询问枚举出的数,不能暴力计算方案数,计算每个结果出现的次数即可。

详细题解

先将A数组排序,方便后续处理
枚举gcd是[一些质数的积的倍数],假设这个积为now, 那么要求B数组中每个数都是now的倍数,才能满足B数组的gcd是now的倍数。

对于一个给定的now值,如何求B数组中每个数都是now的倍数的方案呢?
由于1<=B[i]<=A[i],要求B[i]是now的倍数,那么B[i]就有A[i]/now向下取整种可能性,每个B[i]相互独立,将A[i]/now求积即可,但是这样做很容易就超时了。
令t = A[i]/now。发现t的范围是A[1]/now到A[n]/now,如果now比较大的话,这个范围会非常的小。考虑枚举这个t值,求有多少个A[i]满足A[i]/now=t就好了。
由于A数组已经排好序了,对于一个t,那么最小的一个数x使得x/now = t的就是x = now * t,最大的一个y是y=(t+1)*now-1,
在A数组中查找第一个大于等于x的数,查找第一个大于y的数,这两个位置相减,就是满足A[i]/now=t的i的个数len。
最后用快速幂powMod(t,len)来表示A[i]/now = t这len个数除以now向下取整之后的积,再将不同的t得到的乘起来,得到[B数组中每个数都是now的倍数的方案数]。

枚举这个now值的时候会发现,如果枚举了now1和now2,就会造成now1*now2这个值的方案数会算重,需要用容斥减去。
枚举是否选每一个质数,如果选了奇数个质数,那么答案+上这奇数个数造成的方案数,否则ans-去这偶数个数造成的方案数。
如何进行枚举?
用dfs枚举是否选择每一个质数,用k记录已经选的质数的积,用一个变量f,值为1或-1来记录已经选取的质数的个数的奇偶性, now代表正在枚举是否选这个数的下标。
首先,如果now超过了质数的个数,可以return了。
先要明确以点,如果k已经大于了A[1],那么就没用方案了,A[1]怎么可能是一个比他自己还大的数的倍数嘛……
所以假设选取质数p[now],如果p[now] * k > A[1]了,也可以return了
接下来就是算 p[now] *k造成的方案数了,ans += f*造成的方案数。
最后继续进行dfs,枚举是否选这个数,如果选了这个数,k变为k*p[now],f=-f。

 

 

HDU 6047 Maximum Sequence 贪心 优先队列

http://acm.hdu.edu.cn/showproblem.php?pid=6047

Maximum Sequence

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Steph is extremely obsessed with “sequence problems” that are usually seen on magazines: Given the sequence 11, 23, 30, 35, what is the next number? Steph always finds them too easy for such a genius like himself until one day Klay comes up with a problem and ask him about it.
Given two integer sequences {ai} and {bi} with the same length n, you are to find the next n numbers of {ai}: $a_{n+1}…a_{2n}$. Just like always, there are some restrictions on $a_{n+1}…a_{2n}$: for each number $a_i$, you must choose a number $b_k$ from {bi}, and it must satisfy $a_i$≤max{$a_j$-j│$b_k$≤j<i}, and any $b_k$ can’t be chosen more than once. Apparently, there are a great many possibilities, so you are required to find max{$\sum_{n+1}^{2n}a_i$} modulo $10^9$+7 .
Now Steph finds it too hard to solve the problem, please help him.

Input

The input contains no more than 20 test cases.
For each test case, the first line consists of one integer n. The next line consists of n integers representing {ai}. And the third line consists of n integers representing {bi}.
1≤n≤250000, n≤a_i≤1500000, 1≤b_i≤n.

Output

For each test case, print the answer on one line: max{$\sum_{n+1}^{2n}a_i$} modulo $10^9$+7。

 Sample Input

Sample Output

Hint

For the first sample: 1. Choose 2 from {bi}, then a_2…a_4 are available for a_5, and you can let a_5=a_2-2=9; 2. Choose 1 from {bi}, then a_1…a_5 are available for a_6, and you can let a_6=a_2-2=9;

Source

题意

给定两个长度为$n$数组$a_i,b_i$,现在要把$a_i$补充到长度为$2n$,从左到右补充,对于每一个$a_i$,需要选取一个未使用的$b_k$,$a_i$ 为$a$数组在$b_k~i-1$区间内的最小值。求$\sum_{n+1}^{2n}a_i$的最大值。

思路

对于每次取数,尽量取大即可,即使用当前能使用的最小的$b_k$。那么对$b_i$排序,将$a_i-i$放入优先队列,每次将堆顶的不合法元素弹掉,再取值记录答案,再将取出的值减去下标后压入优先队列。

 

 

HDU 6036 I Curse Myself 仙人掌的最小生成树

http://acm.hdu.edu.cn/showproblem.php?pid=6041

I Curse Myself

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

There is a connected undirected graph with weights on its edges. It is guaranteed that each edge appears in at most one simple cycle.
Assuming that the weight of a weighted spanning tree is the sum of weights on its edges, define $V(k)$ as the weight of the $k$-th smallest weighted spanning tree of this graph, however, $V(k)$ would be defined as zero if there did not exist $k$ different weighted spanning trees.
Please calculate $\displaystyle\left(\sum_{k=1}^{K}{k \cdot V(k)}\right) \bmod 2^{32}$.

Input

The input contains multiple test cases.
For each test case, the first line contains two positive integers $n, m$ $(2 \leq n \leq 1000, n-1 \leq m \leq 2n-3)$, the number of nodes and the number of edges of this graph.
Each of the next $m$ lines contains three positive integers $x, y, z$ $(1 \leq x, y \leq n, 1 \leq z \leq 10^6)$, meaning an edge weighted $z$ between node $x$ and node $y$. There does not exist multi-edge or self-loop in this graph.
The last line contains a positive integer $K$ $(1 \leq K \leq 10^5)$.

Output

For each test case, output "Case #$x$: $y$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y$ denotes the answer of corresponding case.
Sample Input

Sample Output

Source

 

题意

给一个$n$个点的无向图,保证一条边最多属于一个环,求前$k$小生成树的权重*排名的和。

思路

可以发现这是一颗仙人掌图,对于每一个环来说,最小生成树上会不包含上面的一条边。换句话说,边权的总和,减去每个环上的一条边,就是一颗生成树。那么就是每个环贡献一条边,求这些边和前$k$大值。考虑这$m$个环上的边,构成了$m$个数组,我们只需要对数组两两合并,维护前$k$大值即可。合并的时候采用优先队列,将长度短的数组的每一个数$b_i + a_0$放入优先队列,弹出的时候,记录答案,修改$a$元素为较大的一个后继续放入优先队列(这里$a$数组已经排序)。

 

 

 
 

HDU 6039 Gear Up 并查集 dfs序 线段树

http://acm.hdu.edu.cn/showproblem.php?pid=6039

Gear Up

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

constroy has some gears, each with a radius. Two gears are considered adjacent if they meet one of the following conditions:
1. They share a common edge (i.e. they have equal linear velocity).
2. They share a common shaft (i.e. they have equal angular velocity).
It is guaranteed that no pair of gears meets both of the above conditions.
A series of continuous adjacent gears constitutes a gear path. There is at most one gear path between each two gears.
Now constroy assigns an angular velocity to one of these gears and then asks you to determine the largest angular velocity among them.
sd0061 thinks this problem is too easy, so he replaces some gears and then asks you the question again.

Input

There are multiple test cases (about $30$).
For each test case:
The first line contains three integers $n, m, q$, the number of gears, the number of adjacent pairs and the number of operations. $(0 \leq m < n \leq 10^5, 0 \leq q \leq 10^5)$
The second line contains $n$ integers, of which the $i$-th integer represents $r_i$, the radius of the $i$-th gear. $(r_i \in \{2^\lambda \mid 0 \leq \lambda \leq 30\})$
Each of the next $m$ lines contains three integers $a, x, y$, the $x$-th gear and the $y$-th gear are adjacent in the $a$-th condition. $(a \in \{1, 2\}, 1 \leq x, y \leq n, x \neq y)$
Each of the next $q$ line contains three integers $a, x, y$, an operation ruled in the following: $(a \in \{1, 2\}, 1 \leq x \leq n, y \in \{2^\lambda \mid 0 \leq \lambda \leq 30\})$
$a = 1$ means to replace the $x$-th gear with another one of radius $y$.
$a = 2$ means to assign angular velocity $y$ to the $x$-th gear and then determine the maximum angular velocity.

Output

For each test case, firstly output "Case #$x$:" in one line (without quotes), where $x$ indicates the case number starting from $1$, and then for each operation of $a = 2$, output in one line a real number, the natural logarithm of the maximum angular velocity, with the precision of $3$ digits.

Sample Input

Sample Output

Source

题意

给n个齿轮,每个齿轮都有各自的半径,再给m对齿轮关系,有共边和共轴两种。有q次操作,每次操作会修改某个齿轮的半径,或者是给以某个齿轮一个角速度,问和他连通的齿轮组内角速度最大齿轮的角速度。保证输入的半径或者角速度都是2的整数次方幂。输出的答案取自然对数。保证齿轮关系构成的图没有环。

思路

使用并查集维护共轴的齿轮关系。在每个齿轮连通块中选取一个参考齿轮,将所有的速度和半径对2取对数后,角速度之间差距就从倍数变成了差值,方便计算。从参考齿轮开始,进行dfs,并维护dfs序,优先dfs和这个齿轮共边的齿轮,并计算每个齿轮对于参考齿轮的角速度差,和这个齿轮u共边的齿轮v,他们的角速度都是都是比u的相对角速度快r[u]-r[v],其中r为半径,并且记每个v齿轮在树上的父亲为u。记录下这个dfs序的起止位置为edgeL[u],edgeR[u]。再dfs和这个齿轮共轴的齿轮,这些齿轮的角速度和u相同,并且记这些齿轮的在树上的父亲为不存在。记录这段dfs序列的起止位置为shaftL[u]和shaftR[u]。

询问的时候,先计算出参考齿轮的角速度,再求整个连通块内的最大值即可,区间应该为edgeL[u]~shaftR[u]。

修改分为两种情况。如果这个齿轮在树上没有父亲,那么修改他的半径,只会影响和他共边的齿轮以及共边齿轮连接的齿轮,区间为edgeL[u]+1~edgeR[u]。如果有父亲,则会影响他自己的角速度以及和他共轴齿轮及他们连接的齿轮,区间为edgeL[u]~edgeL[u],shaftL[u]~shaftR[u]。每次修改,对上述区间进行区间累加,维护最大值即可。

 

HDU 6004 Periodical Cicadas 中国剩余定理 + 二维RMQ

http://acm.hdu.edu.cn/showproblem.php?pid=6004


Periodical Cicadas

Time Limit: 14000/7000 MS (Java/Others)    Memory Limit: 80000/80000 K (Java/Others)

Problem Description

Nearly all cicadas spend years underground as juveniles, before emerging above ground for a short adult stage of several weeks to a few months.
The seven periodical cicada species are so named because, in any one location, all of the members of the population are developmentally synchronized they emerge as adults all at once every seven years.
The lifecycles of most periodical cicada species range from two to seventeen years, although some could be longer.
There is a forest which can be roughly divided into a matrix of size N ×M. The upper-left region is (1, 1) and the lower-right region is (N, M).
A population of periodical cicadas live within each region of the matrix. The population in region (i, j) emerged in year $a_{i,j}$ for the first time, and re-emerges every $b_{i,j}$ years. i.e. they are $b_{i,j}$ - periodical cicadas.
Given a selected rectangular area, entomologists wonder if there is a time when all cicadas in that area emerge together.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test cases begin with two integers N and M.
The following N lines each consists of M integers $a_{i,j}$ representing the year cicadas emerged in region (i, j) for the first time.
The following N more lines each consists of M integers $b_{i,j}$ representing the periodical cycle of the cicadas in that region.
Then comes a line with an integer Q representing the number of queries. The following Q lines each consists of 4 integers: $x_1, y_1, x_2, y_2,$ representing the upper-left and lower-right coordinate of the selected rectangular area.

 Output

For each test case, first output one line containing “Case #x:”, where x is the test case number (starting from 1).
The following Q lines each consists of an integer which is the year when all cicadas in the selected area emerge together for the first time or -1 if it’s impossible.

limits

$\bullet 1 ≤ T ≤ 10.$
$\bullet 1 ≤ N, M ≤ 200.$
$\bullet 0 ≤ a_{i,j} < b_{i,j} ≤ 40.$
$\bullet 1 ≤ x_1 ≤ x_2 ≤ N.$
$\bullet 1 ≤ y_1 ≤ y_2 ≤ M.$
$\bullet$ 1 ≤ Q ≤ 500000.

Sample Input

2
3 4
3 1 1 2
1 1 2 1
1 0 5 5
5 4 2 3
2 2 3 2
4 2 6 6
5
2 2 2 2
1 1 3 4
1 4 2 4
1 1 1 2
2 2 3 4
1 2
0 1
2 2
1
1 1 1 2

 Sample Output

Case #1:
1
-1
5
13
-1
Case #2:
-1

 Source

 

题意

在一个n*m的矩阵中,每个格子有一只蝉。每只蝉分别会在$ a_{i,j}$ 时间叫一声,然后每$ b_{i,j}$时间叫一声($0 ≤ a_{i,j} < b_{i,j} ≤ 40.$)。有Q次询问,每次询问从$x_1,y_1$到$x_2,y_2$区域内,所有蝉同时叫的最早的时间,如果不会同时叫,输出-1。

思路

可以把每个蝉看作同余方程,即$t_{i,j} \equiv  a_{i,j}(\mod b_{i,j} )$,每只蝉会在$t_{i,j}$时间叫,询问一个区域的时候,将区域内的所有同余方程用中国剩余定理合并即可。由于重复合并相同的方程不会对结果造成影响,可以使用二维RMQ来预处理区域内的同余方程。要注意在合并方程的时候,会出现乘法超出long long数据范围的问题。

 

HDU5957 Query on a graph 基环树 + BFS序列 + 线段树区间维护

http://acm.hdu.edu.cn/showproblem.php?pid=5957

Query on a graph

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

You are given a connected simple graph(in which both multiple edges and loops are disallowed) with N nodes and N edges. In this graph each node has a weight, and each edge has the same length of one unit. Define D(u,v) as the distance between node u and node v. Define S(u,k) as the set of nodes x which satisfy D(u,x) ≤ k.
We will ask you to perform some instructions of the following forms.
MODIFY u k d: weight of all nodes in S(u,k) increase by d or decrease by -d.
QUERY u k: ask for the sum of weight of all nodes in S(u,k).
In the beginning, the weight of all nodes are 0.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow. For each test case, in the first line there is an integer N(N ≤ 100000). The i-th line of the next N line describes the i-th edge: two integers u,v denotes an edge between u and v. In the next line, an integer Q(Q ≤ 100000) indicates the number of instructions. Next Q lines contain instructions MODIFY u k d or QUERY u k, where |d|≤ 100 and 0 ≤ k ≤ 2.

Output

For each QUERY instruction, output a integer in a line.

Sample Input

2
6
1 2
2 3
3 4
4 1
4 5
3 6
5
MODIFY 1 1 3
MODIFY 3 1 2
MODIFY 5 2 1
QUERY 3 2
QUERY 4 1
6
1
2 2
3 3
1 1
4 2
5 3
6 5
MODIFY 3 1 5
MODIFY 2 2 2
QUERY 6 1
MODIFY 4 1 -2
QUERY 2 2

Sample Output

21
14
14
28

Source

题意

给一个n个点n条边的无向联通图(n <=10w),边权都是1。定义集合d(u,k)为距离 u点不超过k的点集合。有q次操作或者询问(q<=10w),每次操作是吧d(u,k)集合内的点点权加上d,询问是询问d(u,k)集合内所有的点权和。(0<=d<=2)

思路

对于上诉的图,名字叫做基环树。存在一个环,环上的每一个点都是一个树的根。先将这个环找到。这样问题就从图上的询问简化到了树上。由于是询问或者操作一个范围,可以考虑使用BFS序。维护每一个节点他的儿子和孙子的BFS序的最大值和最小值,同一个树的所有儿子的BFS序一定是连续的,孙子的BFS也一定是连续的,对于这个范围操作,可以考虑使用线段树来进行维护。当k=0的时候,就是单点操作,k=1的时候,先操作u的所有儿子和u点,如果u点在环上,还要单点操作u在环上的周围的两个点。当k=2的时候,情况就比较复杂的。情况1:u点在环上,先操作单点u点和u的儿子以及u的孙子,在环上距离u点为1的两个点x,对x进行单点操作,并对x的儿子进行操作,在环上距离u点为2的两个点y,对y进行单点操作。但是要注意环大小为3的时候和4的时候,操作会重复,需要减去多余操作。情况2:u不在环上,先操作单点u点和u的儿子以及u的孙子,再单点操作u的父亲fa,操作fa的儿子,这时候,u点背重复操作,所以前面一次对u的操作可以不做。这时,如果fa在环上,单点操作fa在环上周围的两个点,否则单点操作fa的父亲。
 

 

 

Codeforces158E Dividing Kingdom 暴力枚举 + 可持久化线段树

E. Dividing Kingdom

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A country called Flatland is an infinite two-dimensional plane. Flatland has n cities, each of them is a point on the plane.

Flatland is ruled by king Circle IV. Circle IV has 9 sons. He wants to give each of his sons part of Flatland to rule. For that, he wants to draw four distinct straight lines, such that two of them are parallel to the Ox axis, and two others are parallel to the Oy axis. At that, no straight line can go through any city. Thus, Flatland will be divided into 9 parts, and each son will be given exactly one of these parts. Circle IV thought a little, evaluated his sons' obedience and decided that the i-th son should get the part of Flatland that has exactly aicities.

Help Circle find such four straight lines that if we divide Flatland into 9 parts by these lines, the resulting parts can be given to the sons so that son number i got the part of Flatland which contains ai cities.

Input

The first line contains integer n (9 ≤ n ≤ 105) — the number of cities in Flatland. Next n lines each contain two space-separated integers: xi, yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th city. No two cities are located at the same point. The last line contains nine space-separated integers: .

Output

If there is no solution, print a single integer -1.

Otherwise, print in the first line two distinct real space-separated numbers: x1, x2 — the abscissas of the straight lines that are parallel to the Oy axis. And in the second line print two distinct real space-separated numbers: y1, y2 — the ordinates of the straight lines, parallel to the Ox. If there are multiple solutions, print any of them.

When the answer is being checked, a city is considered to lie on a straight line, if the distance between the city and the line doesn't exceed 10 - 6. Two straight lines are considered the same if the distance between them doesn't exceed 10 - 6.

Examples

input

output

input

output

input

output

Note

The solution for the first sample test is shown below:

The solution for the second sample test is shown below:

There is no solution for the third sample test.

题意:

将平面用两条垂直于x轴的直线和两条垂直与y轴的直线划分成如图所示的九个区域,要求每个区域内的点为一定的数目(顺序随意),问这四条直线的坐标。如果不能输出-1。

思路:

先将点离散化,再插入按y值建树的可持久化线段树,每个x值一棵树。这样就可以快速的查一个矩形区域内的点的个数。然后暴力全排列枚举每个区域内点的个数。再用建好的可持久化线段树检查即可。具体方法是根据枚举的区域内的点的个数,可以知道垂直于x轴分出的三个区域内点的个数,这样就可以确定直线的x值,再这样确定两个y值。再分别检查划分出的区域内的点是否和枚举的相同。如果相同,就可以输出了。

 

 

Codeforces 750E New Year and Old Subsequence 线段树优化区间DP

E. New Year and Old Subsequence

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A string t is called nice if a string "2017" occurs in t as a subsequence but a string "2016" doesn't occur in t as a subsequence. For example, strings "203434107" and "9220617" are nice, while strings "20016", "1234" and "20167" aren't nice.

The ugliness of a string is the minimum possible number of characters to remove, in order to obtain a nice string. If it's impossible to make a string nice by removing characters, its ugliness is  - 1.

Limak has a string s of length n, with characters indexed 1 through n. He asks you q queries. In the i-th query you should compute and print the ugliness of a substring (continuous subsequence) of s starting at the index ai and ending at the index bi (inclusive).

Input

The first line of the input contains two integers n and q (4 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) — the length of the string s and the number of queries respectively.

The second line contains a string s of length n. Every character is one of digits '0'–'9'.

The i-th of next q lines contains two integers ai and bi (1 ≤ ai ≤ bi ≤ n), describing a substring in the i-th query.

Output

For each query print the ugliness of the given substring.

Examples

input

output

input

output

input

output

Note

In the first sample:

  • In the first query, ugliness("20166766") = 4 because all four sixes must be removed.
  • In the second query, ugliness("2016676") = 3 because all three sixes must be removed.
  • In the third query, ugliness("0166766") =  - 1 because it's impossible to remove some digits to get a nice string.

In the second sample:

  • In the second query, ugliness("01201666209167") = 2. It's optimal to remove the first digit '2' and the last digit '6', what gives a string "010166620917", which is nice.
  • In the third query, ugliness("016662091670") = 1. It's optimal to remove the last digit '6', what gives a nice string "01666209170".

题意

给定一个长度小于10w的数字序列,每次询问一个区间,删除最少的字符后,能包含2017子序列但是不包含2016子序列。

思路

用线段树维护一个dp[i][j]表示从区间的起点,起始位状态i,到区间的终点,状态为j的时候的所需要删除的字符的最少的个数。其中0表示前面没有包含任何关于“2017”的子序列,1表示包含子序列1,2表示包含子序列12,依次类推,特别注意在3、4状态的时候的花费。不可能的状态标记为-1即可。查询的合并下区下区间的DP值即可。