{"problem":{"name":"Parenthesis Checking","description":{"content":"Let us define a **correct parenthesis sequence** as a string that satisfies one of the following conditions. *   It is an empty string. *   It is a concatenation of `(`, $A$, `)`, in this order, for ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc223_f"},"statements":[{"statement_type":"Markdown","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**.\n\n## Constraints\n\n*   $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`.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc223_f","tags":[],"sample_group":[["5 3\n(())(\n2 1 4\n2 1 2\n2 4 5","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**."],["5 3\n(())(\n2 1 4\n1 1 4\n2 1 4","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**."],["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","Yes\nNo\nNo"]],"created_at":"2026-03-03 11:01:13"}}