문제

0과 1만으로 이루어진 길이 이상의 문자열 가 다음 조건 중 하나를 만족하는 경우, 이러한 를 그룹 문자열이라고 부릅니다.

• 에 0이 등장하지 않거나 1이 등장하지 않습니다.
• 에서 모든 0은 모든 1보다 먼저 등장합니다.
• 에서 모든 1은 모든 0보다 먼저 등장합니다.

예를 들어, 000, 11, 00111, 110은 그룹 문자열이지만, 1011이나 00100은 그룹 문자열이 아닙니다.

0과 1만으로 이루어진 문자열 에 대해, 의 처음과 끝에서 문자를 원하는 만큼 지워 만들 수 있는 서로 다른 그룹 문자열의 개수를 라고 정의합니다. 예를 들어, 가 10110일 때 만들 수 있는 그룹 문자열은 0, 01, 011, 1, 10, 11, 110이 있습니다. 그러므로 가 10110일 때 의 값은 입니다. 이때 10이 에 여러 번 등장하지만 를 구하는 데는 한 번만 세는 것에 유의하세요.

여러분에게 문자열 에 대한 번의 질문이 주어집니다. 초기에 문자열 는 빈 문자열입니다. 각 질문은 다음과 같은 형태입니다.

• : 문자열 의 끝에 문자 를 개 붙입니다. 그후 의 값을 구합니다.

이때 질문으로 문자열 에 추가된 문자는 그다음 질문이 주어질 때에도 문자열 에서 지워지지 않고 남아있습니다.

여러분은 각 질문에 대해 충분히 빨리 대답할 수 있을까요?

입력

첫 번째 줄에 정수 가 주어집니다.

두 번째 줄부터 개의 줄에 걸쳐 각 줄에 질문에 대응되는 문자 와 양의 정수 가 주어집니다.

출력

개의 줄에 걸쳐 각 줄에 질문에 대한 정답을 출력합니다.

채점

• 각 에 대해 는 0 또는 1
• 각 에 대한 의 합은 이하

서브태스크

노트

예제의 각 질문에 대해 새로운 문자열 의 내용, 새롭게 만들 수 있는 그룹 문자열, 그리고 의 값은 다음과 같습니다.