어린 양의 안식

욱제는 두 팀이 서로 싸우는 게임 리그 오브 레전드를 하고 있다. 각 플레이어는 체력 $h$와 최대 체력 $H$라는 두 정수로 상태를 나타낼 수 있는 챔피언을 조종한다. 챔피언의 체력이 0 이하이면($h \le 0$) 챔피언은 즉시 죽어서 $h = 0$인 채로 게임에서 이탈한다. 챔피언의 체력이 최대 체력보다 크면($h > H$) 최대 체력으로 조정된다. $H$는 항상 양의 정수이다.

한타에서 챔피언의 체력은 오르거나 내릴 수 있다. 더 구체적으로, 한타 동안 챔피언은 $n$개의 행동을 겪는다. $i$번째($1 \le i \le n$) 행동은 위 규칙에 따라 챔피언의 체력을 $a_i$만큼 증가시킨다. $a_i$가 양수면 챔피언이 회복된 것이고, $a_i$가 음수면 공격받은 것이다. $a_i$가 0이면 챔피언에게 아무 일도 일어나지 않는다.

욱제가 리그 오브 레전드에서 가장 좋아하는 챔피언은 킨드레드라는 이름의 어린 양이다. 킨드레드는 어린 양의 안식이라는 궁극기를 가지고 있다. 이 능력이 무엇을 하는지 살펴보자.

형식적으로, 최대 체력이 $H$인 챔피언을 생각하자. 욱제가 $l$번째 행동 직전부터 $r$번째 행동 직후까지 어린 양의 안식을 사용하면, 이 행동들 동안 챔피언의 체력은 $\lceil \frac{H}{10} \rceil$ 아래로 내려가지 않는다. $l$번째 행동 직전에 챔피언의 체력이 $\lceil \frac{H}{10} \rceil$ 이하였거나, 어떤 $l \le i \le r$에 대해 $i$번째 행동 후에 가정상 $\lceil \frac{H}{10} \rceil$ 이하가 된다면, 체력은 $\lceil \frac{H}{10} \rceil$로 설정되고 $r$번째 행동이 끝난 뒤까지 더 이상 변하지 않는다. 그렇지 않으면 어린 양의 안식은 챔피언의 체력 변화에 영향을 주지 않는다.

어린 양의 안식을 언제 사용할지 올바르게 결정하는 것은 매우 중요하다. 욱제는 판단력을 기르고 싶다. 하지만 한타는 너무 복잡해서 어린 양의 안식을 언제 사용해야 할지 알기 어렵다. 그를 돕기 위해 다음 $q$개의 질의를 처리하자.

• 1 l r x: 챔피언의 최대 체력은 $x$이고 체력은 $x$에서 시작한다. $l$번째 행동 직전부터 $r$번째 행동 직후까지 어린 양의 안식이 활성화된다. $n$개의 행동이 끝난 뒤 챔피언의 체력을 출력한다. 챔피언이 죽으면 0을 출력한다. $(1 \le l \le r \le n, 1 \le x \le 10^9)$.
• 2 i x: $a_i$를 $x$로 갱신한다. $(1 \le i \le n, -10^9 \le x \le 10^9)$.

첫째 줄에 두 정수 $n$과 $q$가 주어진다. $(1 \le n, q \le 300\,000)$

둘째 줄에 $n$개의 정수가 주어진다. $i$번째 정수는 $a_i$이다. $(|a_i| \le 10^9)$

다음 $q$개의 줄에 설명한 형태의 질의를 나타내는 정수들이 주어진다.

1번 질의는 적어도 하나 주어진다.

각 1번 질의에 대해 답을 나타내는 정수를 한 줄에 하나씩 출력한다.