{"raw_statement":[{"iden":"problem statement","content":"Let us define a **correct parenthesis sequence** as a string that satisfies one of the following conditions.\n\n*   It is an empty string.\n*   It is a concatenation of `(`, $A$, `)`, in this order, for some **correct parenthesis sequence** $A$.\n*   It is a concatenation of $A$, $B$, in this order, for some **correct parenthesis sequences** $A$ and $B$.\n\nWe have a string $S$ of length $N$ consisting of `(` and `)`.\nGiven $Q$ queries $\\text{Query}_1,\\text{Query}_2,\\ldots,\\text{Query}_Q$, process them in order. There are two kinds of queries, with the following formats and content.\n\n*   `1 l r`: Swap the $l$\\-th and $r$\\-th characters of $S$.\n*   `2 l r`: Determine whether the contiguous substring from the $l$\\-th through the $r$\\-th character is a **correct parenthesis sequence**."},{"iden":"constraints","content":"*   $1 \\leq N,Q \\leq 2 \\times 10^5$\n*   $S$ is a string of length $N$ consisting of `(` and `)`.\n*   $1 \\leq l < r \\leq N$\n*   $N,Q,l,r$ are all integers.\n*   Each query is in the format `1 l r` or `2 l r`.\n*   There is at least one query in the format `2 l r`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $Q$\n$S$\n$\\text{Query}_1$\n$\\text{Query}_2$\n$\\vdots$\n$\\text{Query}_Q$"},{"iden":"sample input 1","content":"5 3\n(())(\n2 1 4\n2 1 2\n2 4 5"},{"iden":"sample output 1","content":"Yes\nNo\nNo\n\nIn the first query, `(())` is a **correct parenthesis sequence**.\nIn the second query, `((` is not a **correct parenthesis sequence**.\nIn the third query, `)(` is not a **correct parenthesis sequence**."},{"iden":"sample input 2","content":"5 3\n(())(\n2 1 4\n1 1 4\n2 1 4"},{"iden":"sample output 2","content":"Yes\nNo\n\nIn the first query, `(())` is a **correct parenthesis sequence**.\nIn the second query, $S$ becomes `)()((`.\nIn the third query, `)()(` is not a **correct parenthesis sequence**."},{"iden":"sample input 3","content":"8 8\n(()(()))\n2 2 7\n2 2 8\n1 2 5\n2 3 4\n1 3 4\n1 3 5\n1 1 4\n1 6 8"},{"iden":"sample output 3","content":"Yes\nNo\nNo"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}