AT_abc331_f [ABC331F] Palindrome Query

[problemUrl]: https://atcoder.jp/contests/abc331/tasks/abc331_f 英小文字からなる長さ $ N $ の文字列 $ S $ が与えられます。 以下で説明されるクエリを与えられる順に $ Q $ 個処理してください。 クエリは次の $ 2 $ 種類のいずれかです。 - `1 x c` : $ S $ の $ x $ 文字目を英小文字 $ c $ に変更する。 - `2 L R` : $ S $ の $ L $ 文字目から $ R $ 文字目までからなる部分文字列が回文であるならば `Yes` を、そうでないならば `No` を出力する。

入力は以下の形式で標準入力から与えられる。ここで $ \text{query}_i $ は $ i $ 番目に処理するクエリである。 > $ N $ $ Q $ $ S $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ 各クエリは以下のいずれかの形式で与えられる。 > $ 1 $ $ x $ $ c $ > $ 2 $ $ L $ $ R $

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^6 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ S $ は英小文字からなる長さ $ N $ の文字列 - $ 1\ \leq\ x\ \leq\ N $ - $ c $ は英小文字 - $ 1\ \leq\ L\ \leq\ R\ \leq\ N $ - $ N,\ Q,\ x,\ L,\ R $ は整数 ### Sample Explanation 1 はじめ、$ S\ = $ `abcbacb` です。 $ 1 $ 番目のクエリについて、$ S $ の $ 1 $ 文字目から $ 5 $ 文字目までからなる文字列は `abcba` で、これは回文です。よって `Yes` を出力します。 $ 2 $ 番目のクエリについて、$ S $ の $ 4 $ 文字目から $ 7 $ 文字目までからなる文字列は `bacb` で、これは回文ではありません。よって `No` を出力します。 $ 3 $ 番目のクエリについて、$ S $ の $ 2 $ 文字目から $ 2 $ 文字目までからなる文字列は `b` で、これは回文です。よって `Yes` を出力します。 $ 4 $ 番目のクエリについて、$ S $ の $ 5 $ 文字目を `c` に変更します。$ S $ は `abcbccb` になります。 $ 5 $ 番目のクエリについて、$ S $ の $ 1 $ 文字目から $ 5 $ 文字目までからなる文字列は `abcbc` で、これは回文ではありません。よって `No` を出力します。 $ 6 $ 番目のクエリについて、$ S $ の $ 4 $ 文字目から $ 7 $ 文字目までからなる文字列は `bccb` で、これは回文です。よって `Yes` を出力します。 $ 7 $ 番目のクエリについて、$ S $ の $ 4 $ 文字目を `c` に変更します。$ S $ は `abccccb` になります。 $ 8 $ 番目のクエリについて、$ S $ の $ 3 $ 文字目から $ 6 $ 文字目までからなる文字列は `cccc` で、これは回文です。よって `Yes` を出力します。