Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem D: Sub Sequence Problem

Problem D: Sub Sequence Problem

Time Limit: 10 Sec  Memory Limit: 150 MB
Submit: 27  Solved: 3
[Submit][Status][Web Board]

Description

In an integer sequence of length N a1,a2,…,aN, the LCNS problem means the Longest Consecutive Non-decrease Sub-sequence problem. For example, the LCNS of sequence (1, 0, 1, 2, 3, 2, 5) is (0, 1, 2, 3).

You are given an integer sequence of length N a1,a2,…,aN, perform Q operation efficiently. There are two kinds of operation:

1.        Add L R v: every elements in range [L, R] inclusive will plus v.

2.        Q L R: output the length of LCNS of sub sequence aL,aL+1,…,aR

 

For simplification, we consider all integer in Mod 10 system, which means an integer X plus Y will become (X+Y)%10. For example, 9 plus 1 will become 0, 8 plus 8 will become 6.

Input

The input contains several test cases (<=10).

For each test case, the first line contains two integer N Q (1<=N<=100,000, 1<=Q<=100,000). The second line follows N integer of initial sequence value (0 <= ai <10). Then comes Q operation (1<=L<=R<=N, 0<=v<10).

 

Output

For each test case, output “Case #c:” first, then for each operation of type 2 output the answer.

Sample Input

5 3
0 1 2 3 4
Q 1 5
Add 2 3 8
Q 2 5
4 3
0 0 0 0
Q 1 4
Add 2 3 7
Q 1 4

Sample Output

Case #1:
5
3
Case #2:
4
3

HINT

[Submit][Status][Web Board]