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.

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).

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