AT_pakencamp_2024_day2_f French Restaurant

フランス料理店「パケンシェ」のシェフであるパケン氏は、ディナータイムに備えて $ N $ 個の料理を用意し、左右一列に並べた。それぞれの料理は $ 1 $ 以上 $ K $ 以下の整数で表される**おいしさ**という値を持っており、現在、左から $ i $ 番目の料理のおいしさは $ D_i $ である。パケンシェでは、おいしさがそれぞれ $ 1, 2, \ldots, K $ である料理をこの順で $ 1 $ つずつ提供するコース料理が非常に人気となっている。 訪れた客になるべく満足してもらうよう、パケン氏はこれら $ N $ 個の料理に対して以下のような $ Q $ 回の行動を行った。 $ i $ 回目の行動の種類は $ 1 $ 以上 $ 3 $ 以下の整数 $ T_i $ で表され、それぞれ以下のような内容である。 - $ T_i = 1 $ の場合、料理の作り直しを行い、 $ L_i $ 番目から $ R_i $ 番目の全ての料理を、おいしさが $ V_i $ の料理に変更した。 - $ T_i = 2 $ の場合、料理にトッピングを行い、 $ L_i $ 番目から $ R_i $ 番目のおいしさが $ K $ 未満であった料理のおいしさを $ 1 $ 増加させた。しかしながら、トッピング前においしさが $ K $ であった料理は非常に繊細な料理であったことから、おいしさが $ 1 $ に変化した。 - $ T_i = 3 $ の場合、次のような思考実験を行った：「ディナータイムに $ 10^{100} $ 人の客が来たとする。 $ L_i $ 番目から $ R_i $ 番目までの料理を、左の料理から順に誰か一人の客に提供する。このとき、おいしさがそれぞれ $ 1,2, \ldots, K $ である料理をこの順で $ 1 $ つずつ提供した客の人数を最大で何人にできるだろうか？」 なお、この思考実験によって料理のおいしさが変化したり、料理がなくなることはない。 パケン氏の弟子であるあなたは、パケン氏の思考実験それぞれに対して、正しい答えを求める必要がある。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ D_1 $ $ D_2 $ $ \ldots $ $ D_N $ $ Q $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各 $ \mathrm{query}_i $ にはいくつかの整数が空白区切りで書かれており、その $ 1 $ つ目が $ T_i $ である。 $ \mathrm{query}_i $ は以下のいずれかの形式である。 > $ 1 $ $ L_i $ $ R_i $ $ V_i $ > $ 2 $ $ L_i $ $ R_i $ > $ 3 $ $ L_i $ $ R_i $

思考実験の回数を $ q $ として、 $ q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目の思考実験における答えを出力せよ。

### 小課題 1. ( $ 1 $ 点) $ K = 1 $ 2. ( $ 9 $ 点) $ N, Q \leq 2000 $ 3. ( $ 30 $ 点) $ K = 2 $ 4. ( $ 15 $ 点) $ T_i = 1, 3 (1 \leq i \leq Q) $ 5. ( $ 15 $ 点) $ T_i = 2, 3 (1 \leq i \leq Q) $ 6. ( $ 30 $ 点) 追加の制約はない ### Sample Explanation 1 パケン氏は $ 10 $ 個の料理を用意し、おいしさは順に $ (1, 2, 3, 4, 5, 1, 2, 3, 4, 5) $ になっています。これからパケン氏は $ 10 $ 回の行動をします： - $ 1 $ 回目の行動では、 $ 1 $ 番目から $ 10 $ 番目の料理における思考実験を行う。 $ 1 $ 番目から $ 5 $ 番目の料理を $ 1 $ 人目の客に提供し、 $ 6 $ 番目から $ 10 $ 番目の料理を $ 2 $ 人目の客に提供することで、 $ 2 $ 人の客にコース料理を提供することができる。 $ 3 $ 人以上の客に提供することはできないので、答えは $ 2 $ となる。 - $ 2 $ 回目の行動では、 $ 1 $ 番目から $ 7 $ 番目の料理における思考実験を行う。 $ 1 $ 番目から $ 5 $ 番目の料理を $ 1 $ 人の客に提供することで、 $ 1 $ 人の客にコース料理を提供することができる。 $ 2 $ 人以上の客に提供することはできないので、答えは $ 1 $ となる。 - $ 3 $ 回目の行動では、作り直しを行い $ 5 $ 番目から $ 7 $ 番目の料理をおいしさが $ 2 $ の料理に変更する。おいしさは順に $ (1, 2, 3, 4, 2, 2, 2, 3, 4, 5) $ になる。 - $ 4 $ 回目の行動では、トッピングを行い $ 5 $ 番目から $ 7 $ 番目の料理のおいしさを $ 1 $ 増加させる。おいしさは順に $ (1, 2, 3, 4, 3, 3, 3, 3, 4, 5) $ になる。 - $ 5 $ 回目の行動では、トッピングを行い $ 5 $ 番目から $ 7 $ 番目の料理のおいしさを $ 1 $ 増加させる。おいしさは順に $ (1, 2, 3, 4, 4, 4, 4, 3, 4, 5) $ になる。 - $ 6 $ 回目の行動では、トッピングを行い $ 5 $ 番目から $ 7 $ 番目の料理のおいしさを $ 1 $ 増加させる。おいしさは順に $ (1, 2, 3, 4, 5, 5, 5, 3, 4, 5) $ になる。 - $ 7 $ 回目の行動では、 $ 1 $ 番目から $ 10 $ 番目の料理における思考実験を行う。 $ 1 $ 番目から $ 5 $ 番目の料理を $ 1 $ 人の客に提供することで、 $ 1 $ 人の客にコース料理を提供することができる。 $ 2 $ 人以上の客に提供することはできないので、答えは $ 1 $ となる。 - $ 8 $ 回目の行動では、作り直しを行い $ 6 $ 番目から $ 7 $ 番目の料理をおいしさが $ 2 $ の料理に変更する。おいしさは順に $ (1, 2, 3, 4, 5, 2, 2, 3, 4, 5) $ になる。 - $ 9 $ 回目の行動では、作り直しを行い $ 6 $ 番目から $ 6 $ 番目の料理をおいしさが $ 1 $ の料理に変更する。おいしさは順に $ (1, 2, 3, 4, 5, 1, 2, 3, 4, 5) $ になる。 - $ 10 $ 回目の行動では、 $ 1 $ 番目から $ 10 $ 番目の料理における思考実験を行う。 $ 1 $ 番目から $ 5 $ 番目の料理を $ 1 $ 人目の客に提供し、 $ 6 $ 番目から $ 10 $ 番目の料理を $ 2 $ 人目の客に提供することで、 $ 2 $ 人の客にコース料理を提供することができる。 $ 3 $ 人以上の客に提供することはできないので、答えは $ 2 $ となる。 ### Constraints - $ 1 \leq N, Q \leq 150000 $ - $ 1 \leq K \leq 5 $ - $ 1 \leq D_i \leq K $ ( $ 1 \leq i \leq N $ ) - $ T_i $ は $ 1, 2, 3 $ のいずれか - $ 1 \leq L_i \leq R_i \leq N $ ( $ 1 \leq i \leq Q $ ) - $ T_i = 1 $ ならば、 $ 1 \leq V_i \leq K $ ( $ 1 \leq i \leq Q $ ) - 入力は全て整数