While rummaging through things in a distant drawer, Anya found a beautiful string $s$ consisting only of zeros and ones.

Now she wants to make it even more beautiful by performing $q$ operations on it.

Each operation is described by two integers $i$ ($1 \le i \le |s|$) and $v$ ($v \in \{0, 1\}$) and means that the $i$-th character of the string is assigned the value $v$ (that is, the assignment $s_i = v$ is performed).

But Anya loves the number $1100$, so after each query, she asks you to tell her whether the substring "1100" is present in her string (i.e. there exist such $1 \le i \le |s| - 3$ that $s_{i}s_{i + 1}s_{i + 2}s_{i + 3} = \texttt{1100}$).

Input

The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of the test case contains the string $s$ ($1 \leq |s| \leq 2 \cdot 10^5$), consisting only of the characters "0" and "1". Here $|s|$ denotes the length of the string $s$.

The next line contains an integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of queries.

The following $q$ lines contain two integers $i$ ($1 \leq i \leq |s|$) and $v$ ($v \in \{0, 1\}$), describing the query.

It is guaranteed that the sum of $|s|$ across all test cases does not exceed $2 \cdot 10^5$. It is also guaranteed that the sum of $q$ across all test cases does not exceed $2 \cdot 10^5$.

Output

For each query, output "YES", if "1100" is present in Anya's string; otherwise, output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

见题面 Input 部分

见题面 Output 部分