Balanced bracket strings and queries

This problem was adapted lightly from an online judge problem that inspired the author.

Balanced bracket string is a property of strings defined as follows.

• The empty string $\varnothing$ is a balanced bracket string.
• If $\mathbf{A}$ is a balanced bracket string, then $\mathtt{\color{#e74c3c}{(}} \mathbf{A} \mathtt{\color{#e74c3c}{)}}$, which wraps $\mathbf{A}$ in brackets, is also a balanced bracket string.
• If $\mathbf{A}$ and $\mathbf{B}$ are balanced bracket strings, then $\mathbf{A} \mathbf{B}$, their concatenation, is also a balanced bracket string.

You are given a string $S$ of length $n$ made only of '(', ')', and '*'. You must process $q$ queries of the following two types.

• 1 $i \,\, c$: Replace the $i$-th character of $S$ with $c$. $c$ is one of '(', ')', '*'. ($1 \le i \le n$)
• 2 $l \,\, r$: Replace each '*' in the substring $S_lS_{l+1}\cdots S_{r-1}S_r$ with '(', ')', or the empty string $\varnothing$, choosing freely for each one. Then concatenate the remaining characters in their original order. Determine whether the result can be a balanced bracket string. ($1 \le l \le r \le n$)

Can you solve all queries fast enough?

The first line contains the length $n$ of $S$ and the number of queries $q$, separated by a space. ($1 \le n,q \le 3\cdot 10^5$)

The second line contains the string $S$ of length $n$. Every character of $S$ is one of '(', ')', '*'.

The next $q$ lines each contain one query, one of the two types described above.

For each query of type 2, print 'Yes' if the substring can be turned into a balanced bracket string, and 'No' otherwise, each on its own line.