Vladik and Entertaining Flags

Vladik은 여가 시간에 깃발의 아름다움을 평가한다.

각 깃발은 양의 정수로 이루어진 n × m 행렬로 나타낼 수 있다.

깃발의 아름다움을 행렬에 있는 컴포넌트의 수로 정의하자. 같은 수가 적힌 칸들의 집합 중, 그 집합에 속한 임의의 두 칸 사이에 같은 컴포넌트에 속한 인접한 칸들을 지나는 경로가 존재하는 것을 컴포넌트라고 한다. 다음은 어떤 깃발 행렬을 컴포넌트로 분할한 예이다.

하지만 이번에는 이 과정에 변화를 주기로 했다. 이제 그는 깃발 전체가 아니라 어떤 구간을 평가하려 한다. 깃발의 구간은 서로 마주 보는 두 꼭짓점이 (1, l)와 (n, r)이고, 조건 1 ≤ l ≤ r ≤ m를 만족하는 깃발 행렬의 부분 행렬로 나타낼 수 있다.

Help Vladik는 주어진 깃발의 몇몇 구간에 대한 아름다움을 계산하려 한다.

첫째 줄에는 공백으로 구분된 세 정수 n, m, q (1 ≤ n ≤ 10, 1 ≤ m, q ≤ 105)가 주어지며, 각각 깃발 행렬의 크기와 구간의 수를 나타낸다.

다음 n개의 각 줄에는 깃발 행렬을 나타내는 공백으로 구분된 m개의 정수가 주어진다. 깃발 행렬의 모든 원소는 106을 초과하지 않는 양의 정수이다.

다음 q개의 각 줄에는 Vladik이 아름다움을 알고 싶어 하는 구간의 경계인 공백으로 구분된 두 정수 l, r (1 ≤ l ≤ r ≤ m)가 주어진다.

각 구간의 결과를 해당하는 줄에 출력한다.

첫 번째 테스트 케이스의 각 구간을 컴포넌트로 분할한 모습은 다음과 같다.