시간 제한메모리 제한제출정답맞은 사람정답 비율
4 초 1024 MB594411.111%

문제

당신은 길을 가다가 수상한 계산기를 발견했다. 계산기를 줍는 그때, 뒤에서 살인마가 나타났고, 당신은 열심히 달려 도망쳤지만 결국 막다른 길에 다다르고 말았다. 뒤에서 들려오는 '게임을 시작하지'라는 말과 함께 계산기에 수식이 나타났다. 그렇게 목숨을 건 게임이 시작되었다.

게임은 계산기의 수식을 계산하면 되는 간단한 게임이다. 하지만 고장난 계산기와 함께하는 이 게임의 규칙을 따르는 것은 쉽지 않다.

  1. 수식의 길이는 N이며 0부터 9까지의 숫자, '+', '*'의 연산기호로 이루어져 있다.
  2. 수식의 값을 계산할 때 수식의 맨 앞에 오거나, 바로 앞에 연산기호가 오는 연산기호는 모두 무시한다. 그 후 수식의 맨 끝에 위치한 문자가 연산기호라면, 해당 연산기호 또한 무시한다.
  3. 수식의 값을 계산할 때 '*' 연산은 '+' 연산보다 먼저 계산한다.
  4. 수식의 값은 항상 109+7로 나눈 나머지로 계산한다.
  5. 단, 연산기호밖에 없는 수식의 값은 -1이다.

예를 들어 '**11+*3*+5++'와 같은 수식이 있다면 '11+3*5'로 생각하여 26이라고 답해야 하고,  '**+++**+++'와 같은 수식이 있다면 -1이라고 답해야 한다.

원래는 이렇게 수식의 값을 계산하고 게임을 끝낼 생각이었지만... 수상할 정도로 레이팅이 높은 참가자들이 쿼리 문제를 넣어달라는 압력을 지속적으로 가했기 때문에, 계산기에 적힌 수식은 Q번에 걸쳐 변화하게 되었다.

한 번의 수식의 변화는 l r x 로 나타낼 수 있다. 이는 수식의 l번째 문자부터 r번째 문자까지의 숫자에 x를 더한다는 뜻이다. 단, 쿼리를 처리할 때만 특별히 '+', '*'도 숫자로 취급하며, 두 문자의 값은 각각 10과 11이다. 만약 더한 결과가 12 이상이 될 경우 12로 나눈 나머지를 적용한다.

계산기 화면에 나타나는 총 Q+1개의 수식의 값을 모두 계산하여 목숨을 건 게임에서 살아남자!

입력

첫째 줄에 N(1 ≤ N ≤ 100,000), Q(1 ≤ Q ≤ 100,000)가 주어진다.

둘째 줄에 길이 N의 수식이 주어진다.

셋째 줄부터 Q개의 줄에 한 줄에 하나씩 쿼리가 주어진다. (1 ≤ l ≤ r ≤ N, 1 ≤ x < 12)

출력

첫째 줄에 입력으로 주어진 수식의 값을 109+7로 나눈 나머지를 출력한다. 혹은 수식이 연산기호로만 이루어진 경우 -1을 출력한다.

둘째 줄부터 Q+1번째 줄까지, i번째 줄에 i-1번째 쿼리를 적용한 이후 수식의 값을 109+7로 나눈 나머지를 출력한다. 혹은 수식이 연산기호로만 이루어진 경우 -1을 출력한다.

예제 입력 1

5 3
11+94
1 2 1
1 5 1
4 4 3

예제 출력 1

105
116
165
495

계산해야 하는 수식은 차례대로 '11+94', '22+94', '33*+5', '33*15'이다. 이 중 '33*+5'는 '33*5'로 생각하고 계산해야 한다.

예제 입력 2

5 3
11111
1 5 9
1 5 2
3 3 5

예제 출력 2

11111
-1
0
500

출처

Contest > Semi-Game Cup > Semi-Game Cup 2 I번