현대모비스에서는 운전자와 탑승자의 편의를 위한 인포테인먼트 헤드유닛이 탑재되어 있습니다. 인포테인먼트 헤드유닛은 운전자와 탑승자에게 차량내/외의 다양한 정보를 제공하면서 동시에 내비게이션, 음성인식, 텔레매틱스 서비스, 멀티미디어 기능 등 엔터테인먼트 및 편의 서비스를 통합적으로 제공하는 기기입니다.

n × m 직사각형 격자 모양의 도로가 나 있는 미로가 있습니다. 미로에서 왼쪽 아래 구석의 좌표는 (0, 0), 오른쪽 위 구석의 좌표는 (n, m) 입니다. 정수 좌표 (a, b)에는 표지판이 있습니다. 자동차의 내비게이션 기능과 차량의 주행 능력을 검증하기 위해 미로의 다양한 위치에서 출발하여 표지판까지 최단 경로를 따라 이동한 테스트 기록이 있습니다. 각 테스트는 출발점의 좌표, 남은 연료량에 따른 최대 주행 거리, 표지판 도달 여부가 기록되어 있습니다. 출발점의 위치와 표지판의 위치가 같을 수 있으며, 이때는 최대 주행 거리에 상관없이 항상 표지판에 도달한 것으로 간주합니다.

테스트 기록을 토대로 표지판의 위치를 알아내려 합니다. 예를 들어 n = 3, m = 5이고 테스트 기록이 다음과 같은 경우를 생각해 봅시다.

이때 표지판이 있을 수 있는 좌표는 (2, 4), (2, 5), (3, 3), (3, 4)의 4개입니다.

격자의 가로 길이 n, 세로 길이 m, 테스트 기록을 나타내는 2차원 정수 배열 tests가 매개변수로 주어집니다. 표지판이 있을 수 있는 좌표의 개수를 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 3 ≤ n ≤ 10⁹
• 3 ≤ m ≤ 10⁹
• 1 ≤ tests의 길이 ≤ 250,000
  • tests의 원소는 [x, y, d, flag] 형태의 길이가 4인 정수 배열입니다.
  • 출발점의 좌표가 (x, y), 최대 주행 거리가 d이고, flag가 1인 경우 표지판에 도달했음을, 0인 경우 표지판에 도달하지 못했음을 의미합니다.
  • 0 ≤ x ≤ n
  • 0 ≤ y ≤ m
  • 0 ≤ d ≤ n + m
  • 0 ≤ flag ≤ 1
  • 표지판이 있을 수 있는 좌표가 하나 이상 존재합니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

총 (99,999 + 1) × (99,999 + 1) = 10,000,000,000개의 정수 좌표 중 (99999, 99999)를 제외한 모든 좌표에 표지판이 있을 수 있습니다.

따라서 9,999,999,999를 return 하면 됩니다.

입출력 예 #3

총 (99,999 + 1) × (99,999 + 1) = 10,000,000,000개의 정수 좌표 중 (50000, 50000)으로부터 거리가 3 이하인 좌표 25개를 제외한 모든 좌표에 표지판이 있을 수 있습니다.

따라서 9,999,999,975를 return 하면 됩니다.

입출력 예 #4

5개의 테스트 기록을 모두 만족하는 정수 좌표의 개수는 총 6,535개임을 알 수 있습니다.

따라서 6,535를 return 하면 됩니다.