행렬과 쿼리

길이가 $n$인 행렬로 이루어진 수열 $a_1$, $a_2$, ..., $a_n$이 주어진다. 다음 쿼리를 수행하는 프로그램을 작성하시오. 처음에 모든 행렬은 $2$행 $2$열의 영행렬이다.

• $1$ $l$ $r$ $i$ $j$: $a_l$, $a_{l+1}$, ..., $a_{r}$를 차례대로 곱한 행렬의 $i$행 $j$열의 값을 $1000000009$ ($=10^9+9$)로 나눈 나머지를 출력한다. 만약 차례대로 곱할 수 없다면 대신 -1을 출력한다. 곱이 존재하지만 결과 행렬의 범위를 벗어나는 입력은 주어지지 않는다. ($ 1 \leq l \leq r \leq n$)
• $2$ $i$: $a_i$의 행을 마지막에 하나 추가하고 추가된 행을 $0$으로 채운다. $a_i$의 행이 $3$행 미만인 경우에만 주어진다. ($ 1 \leq i \leq n$)
• $3$ $i$: $a_i$의 마지막 행을 제거한다. $a_i$의 행이 $2$행보다 많은 경우에만 주어진다. ($ 1 \leq i \leq n$)
• $4$ $i$: $a_i$의 열을 마지막에 하나 추가하고 추가된 열을 $0$으로 채운다. $a_i$의 열이 $3$열 미만인 경우에만 주어진다. ($ 1 \leq i \leq n$)
• $5$ $i$: $a_i$의 마지막 열을 제거한다. $a_i$의 열이 $2$열보다 많은 경우에만 주어진다. ($ 1 \leq i \leq n$)
• $6$ $i$ $j$ $k$ $v$: $a_i$의 $j$행 $k$열의 값을 $v$로 변경한다. 행렬의 범위를 벗어나는 입력은 주어지지 않는다. ($ 1 \leq i \leq n;1 \le v \le 10^6$)

첫 번째 줄에 행렬의 개수를 나타내는 정수 $n$이 주어진다. ($1 \le n \le 200\,000$)

두 번째 줄에 주어질 쿼리의 개수를 나타내는 정수 $q$가 주어진다. ($1 \le q \le 200\,000$)

세 번째 줄부터 $q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. $1$번 쿼리는 한 번 이상 주어진다.

주어지는 모든 수는 정수이다.

$1$번 쿼리가 주어질 때마다 쿼리의 답을 한 줄에 하나씩 출력한다.