Conference

Chairman K is going to host a series of conferences over $N$ days. Each day, exactly one conference is held, and it takes place in one of the three venues: the main venue A or one of the sub-venues B and C.

The venue information for each conference is given as a string $S$ consisting of ‘A’, ‘B’, ‘C’, and ‘?’. For the $i$-th day ($1 ≤ i ≤ N$), if the $i$-th character of $S$ is ‘A’, the conference is held in venue A. If it is ‘B’, it is held in venue B. If it is ‘C’, it is held in venue C. If it is ‘?’, the venue for the $i$-th day has not been decided yet. However, since the conferences on the first and $N$-th days are expected to have many participants, it has already been determined that venue A will be used on those days.

Chairman K now needs to assign a venue to each undecided conference, choosing one of A, B, or C for each. Additionally, in order to minimize the burden of moving between venues, he wants to minimize the number of indices $j$ ($1 ≤ j ≤ N - 1$) such that the venue for the $j$-th day differs from the venue for the $(j + 1)$-th day.

There are $Q$ scenarios to consider regarding the assignment of venues. The $k$-th scenario ($1 ≤ k ≤ Q$) and the corresponding question are as follows:

• Chairman K has to assign $X_k$ undecided conferences to venue A, $Y_k$ to venue B, and $Z_k$ to venue C. Determine the minimum possible number of indices $j$ such that the venue for the $j$-th day differs from the venue for the $(j + 1)$-th day.

Given the information about the venues and scenarios to consider, write a program to answer the questions.

Read the following data from the standard input.

$N$

$S$

$Q$

$X_1$ $Y_1$ $Z_1$

$X_2$ $Y_2$ $Z_2$

$\vdots$

$X_Q$ $Y_Q$ $Z_Q$

Write $Q$ lines to the standard output. In the $k$-th line ($1 ≤ k ≤ Q$), output the minimum number of indices $j$ such that the venue for the $j$-th day differs from the venue for the $(j + 1)$-th day, under the condition that Chairman K assigns $X_k$ undecided conferences to venue A, $Y_k$ to venue B, and $Z_k$ to venue C.

• $2 ≤ N ≤ 300\, 000$.
• $S$ is a string of length $N$ consisting of ‘A’, ‘B’, ‘C’, and ‘?’.
• The first and $N$-th characters of $S$ are ‘A’.
• $1 ≤ Q ≤ 200\, 000$.
• $0 ≤ X_k$ ($1 ≤ k ≤ Q$).
• $0 ≤ Y_k$ ($1 ≤ k ≤ Q$).
• $0 ≤ Z_k$ ($1 ≤ k ≤ Q$).
• $X_k + Y_k + Z_k$ is equal to the number of ‘?’ in $S$ ($1 ≤ k ≤ Q$).
• $N$, $Q$, $X_k$, $Y_k$, $Z_k$ are all integers.