시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 512 MB 32 9 5 26.316%

문제

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

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

  • p1 p2 q: 두 부분 문자열 ap1ap1+1...ap1+len-1과 bp2bp2+1...bp2+len-1 의 해밍 거리를 구해 출력한다.

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

입력

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

셋째 줄에는 쿼리의 개수 q (1 ≤ q ≤ 400,000)가 주어진다. 다음 q개의 줄에는 쿼리를 나타내는 p1, p2, len이 주어진다. (0 ≤ p1 ≤ |a|-len, 0 ≤ p2 ≤ |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

출처