Faraway
시간 제한1초메모리 제한512 MB
최대 10개의 조건 각각에 대해 (|xi - xe| + |yi - ye|) mod ki = ti를 만족하는 격자점 (xe, ye)가 [0, m]^2 안에 몇 개인지 세는 문제다. ki는 5 이하이고 m은 1e9까지 커질 수 있다.
문제
n명의 병사로 이루어진 분대가 Byteland의 어딘가로 파견된다. 현재 i번째 병사는 위치 (xi, yi)에 있다. 병사들은 이제 출발하려 하지만, 목표 위치는 명확하지 않다.
목표 위치가 (xe, ye)라고 하자. xe와 ye가 모두 [0, m] 범위의 음이 아닌 정수라는 사실은 모든 병사가 알고 있다. 그 외에 i번째 병사가 아는 것은 (|xi − xe| + |yi − ye|) mod ki = ti 뿐이다.
병사들은 지금 가진 정보를 바탕으로 올바른 목표 위치를 찾으려 한다. 가능한 목표 위치의 개수를 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 T (1 ≤ T ≤ 10)가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 두 정수 n과 m (1 ≤ n ≤ 10, 1 ≤ m ≤ 109)이 주어진다. n은 병사의 수, m은 xe와 ye의 상한이다.
다음 n개의 줄에는 각각 네 정수 xi, yi, ki, ti (0 ≤ xi, yi ≤ m, 2 ≤ ki ≤ 5, 0 ≤ ti < ki)가 주어진다. 이는 i번째 병사가 아는 정보를 나타낸다.
출력
각 테스트 케이스마다 가능한 목표 위치의 개수를 한 줄에 하나의 정수로 출력한다.