길이가 같은 두 바이너리 문자열 s와 t가 주어졌을 때, 해밍 거리는 서로 다른 값을 가진 위치의 개수와 같다. 예를 들어, "00111"과 "10101"의 해밍 거리는 2이다.</p>

두 바이너리 문자열 a와 b가 주어졌을 때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• p1 p2 len: 두 부분 문자열 a_p1ap1+1</sub>...ap1+len-1</sub>과 bp2</sub>bp2+1</sub>...bp2+len-1</sub> 의 해밍 거리를 구해 출력한다.</sub>

문자열의 인덱스는 0번 부터 시작한다.

입력 형식

첫째 줄에 바이너리 문자열 a, 둘째 줄에 바이너리 문자열 b가 주어진다. a와 b의 길이는 200,000보다 작거나 같은 자연수이다.</p>

셋째 줄에는 쿼리의 개수 q (1 ≤ q ≤ 400,000)가 주어진다. 다음 q개의 줄에는 쿼리를 나타내는 p₁, p₂, len이 주어진다. (0 ≤ p₁ ≤ |a|-len, 0 ≤ p₂ ≤ |b|-len)

출력 형식

각각의 쿼리마다 정답을 출력한다.

예제 입력 1

101010
11110000
3
0 0 3
2 3 4
5 7 1

예제 출력 1

1
1
0

예제 입력 2

10001010101011001010100101010011010
101010100101001010100100101010
5
0 0 12
3 9 7
6 4 15
12 15 10
13 3 20

예제 출력 2

5
4
3
5
13