高橋君は次の問題を解いています。

$N$ 個の行列の列 $X$ が与えられる。左から $i$ 番目の行列は $M_{i-1}$ 行 $M_i$ 列である。
$Q$ 個のクエリが順に与えられる。$i$ 番目のクエリは次のような形式である。

• タイプ $1$: 1 x B $x$ 番目の行列を $M_{x-1}$ 行 $M_x$ 列の行列 $B$ に更新する。
• タイプ $2$: 2 l r $l$ 番目から $r$ 番目までの行列の行列積を計算し出力する。

高橋君はこの問題に、下記の条件を満たす二分木を用いて答えます。

• $2N-1$ 個の頂点からなり、各頂点には番号 $1,2,\cdots,2N-1$ がついている。
• 各頂点 $i$ は区間 $[L_i, R_i]$ を持つ。
• 頂点 $1$ は根であり、区間 $[1, N]$ を持つ。
• 頂点 $i$ が葉であるときかつそのときに限り $L_i = R_i$ である。
• 葉でない頂点には $c_i, d_i$ の $2$ 個の子が存在する。また、葉でない頂点が持つ区間を $[i, j]$ とすると、この頂点の子が持つ区間は $[i, k]$ と $[k + 1, j]$ である。（$i \leq k < j$）
• 各頂点 $i$ は、$M_{L_i-1}$ 行 $M_{R_i}$ 列の行列 $A_i$ を持つ。最初、 $A_i$ は $X_{L_i}$ から $X_{R_i}$ までの行列の行列積に等しい。

更に、高橋君は次のような疑似コードを書きました。次の方法によってクエリを処理します。

• タイプ $1$ のクエリが与えられたとき、f(1, x, B) を呼び出し各頂点の持つ行列 $A_i$ を更新する。
• タイプ $2$ のクエリが与えられたとき、g(1, l, r) を呼び出し答えを計算する。

fun f($n$, $x$, $B$):
    if $[L_n, R_n] = [x, x]$:
        $A_n$ = $B$
        return
    if $x \in [L_{c_n}, R_{c_n}]$:
        f($c_n$, $x$, $B$)
    if $x \in [L_{d_n}, R_{d_n}]$:
        f($d_n$, $x$, $B$)
    $A_n$ = mult($A_{c_n}$, $A_{d_n}$)

fun g($n$, $l$, $r$):
    if $[L_n, R_n] \subset [l, r]$:
        return $A_n$
    if $[l, r] \cap [L_{c_n}, R_{c_n}] = \emptyset$:
        return g($d_n$, $l$, $r$)
    if $[l, r] \cap [L_{d_n}, R_{d_n}] = \emptyset$:
        return g($c_n$, $l$, $r$)
    return mult(g($c_n$, $l$, $r$), g($d_n$, $l$, $r$))

fun mult($A$, $B$):
    $C$ = $O_{A.\mathrm{row},B.\mathrm{col}}$
    for $i$ in $[0, A.\mathrm{row})$:
        for $j$ in $[0, B.\mathrm{col})$:
            for $k$ in $[0, A.\mathrm{col})$:
                $C_{i,j}$ += $A_{i,k} * B_{k,j}$
    return $C$

ただし、$O_{n,m}$ は $n$ 行 $m$ 列の零行列、$A.\mathrm{row}, A.\mathrm{col}$ はそれぞれ行列 $A$ の行数、列数を表します。

行列積の計算は重いことに気づいた高橋くんは、二分木をうまく決めることで行列積にかかる計算量を最小化することにしました。
具体的には、$x$ 行 $y$ 列の行列と $y$ 行 $z$ 列の行列の行列積を計算するのにかかるコストを $xyz$ として、すべてのクエリを処理するときにかかるコストの総和を最小化したいです。
あなたは与えられるクエリの内容を事前に知っています。高橋君の代わりに二分木をうまく決め、コストの総和の最小値を求めてください。

• $1 \leq N \leq 500$
• $1 \leq M_i \leq 10^4 (0 \leq i \leq N)$
• $1 \leq Q \leq 1000$
• タイプ $1$ のクエリにおいて、$1 \leq x \leq N$
• タイプ $2$ のクエリにおいて、$1 \leq l \leq r \leq N$
• 入力はすべて整数である。

この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。

1. ($200$ 点)

• $1 \leq N \leq 50$

2. ($200$ 点)

• $1 \leq N \leq 200$

3. ($400$ 点)

• 追加の制約はない。

入力は以下の形式で標準入力から与えられる。

$\mathrm{query_i}$ は $i$ 番目のクエリを表しており、以下のいずれかの形式で与えられる。

行列の列 $X$ や更新される行列 $B$ は入力で与えられないことに注意せよ。

コストの総和としてあり得る最小値を出力せよ。