문제

다다스는 물고기를 아주 좋아해서 물고기 화석 하나를 소중히 간직하고 있다. 이 화석은 총 개의 조각으로 이루어져 있으며, 각 조각은 > 또는 < 중 하나의 모양을 갖는다. 모든 조각은 일렬로 나열되어 있으며, 각 조각은 왼쪽에서부터 번 조각이다.

모그는 다다스가 정말로 물고기를 좋아하는지를 확인해보기 위해 총 번의 행동을 취한다. 각 행동은 다음 두 가지 중 하나이다:

• : 를 만족하는 모든 정수 에 대해 번째 조각을 각각 180도 회전시킨다. 즉 >는 <로, <는 >로 바뀐다.
• : 현재 화석에서 물고기의 개수를 출력한다. 물고기란, 연속된 세 조각이 ><> 또는 <>< 형태를 갖는 경우를 말한다.

다다스는 계산에 약하므로 여러분이 대신해서 모그의 행동을 처리해주어야 한다. 모그의 모든 행동에 올바르게 응답하자.

입력

첫 번째 줄에 양의 정수 이 주어진다. ()

두 번째 줄에 물고기 화석을 이루는 개의 조각이 공백 없이 주어진다. 각 조각은 >또는 <중 하나이다.

세 번째 줄에 양의 정수 가 주어진다. ()

네 번째 줄부터 개의 줄에 걸쳐 1번 또는 2번 쿼리가 주어진다. 2번 쿼리는 최소 한 개 이상 주어진다. ()

출력

2번 쿼리가 주어질 때마다 물고기 화석에서의 물고기의 개수를 출력하여라.

노트

다음은 예제의 초기 물고기 화석 그림이다.

첫 번째 행동인 2에 대해서는 다음과 같이 물고기가 2개 있으므로, 첫 번째 줄에 를 출력해야 한다.

두 번째 행동인 1 4 6은 4번부터 6번 조각을 각각 180도 회전시키는 작업이며, 그 결과 화석은 다음과 같이 변한다.

세 번째 행동인 2에 대해서는 다음과 같이 물고기가 4개 있으므로, 두 번째 줄에 를 출력해야 한다.