D. Шар шувуунууд хайсан нь

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Палпатин эзэн хаан шар шувуунуудыг ихэд таалдаг. Түүнд шинэ Death Star-н зураг төсөл байгаа ба энэ нь $n$ ялгаатай хэрчим, $m$ ялгаатай тойрог агуулна. Хэрчмүүд $1$-с $n$ хүртэл дугаарлагдсан ба тойргууд $1$-с $m$ хүртэл дугаарлагдсан.

Палпатин доорх нөхцөлийг хангах $(i,j) (i

  1. $i,j$ тойргууд $k$ хэрчмийг агуулах шулууны хувьд харилцан тэгш хэмтэй.
  2. $i,j$ тойргууд ерөнхий цэггүй.
  3. $i,j$ тойргууд тэнцүү радиустай.
  4. $k$ хэрчим нь $i,j$ тойргуудын төвүүдийг холбосон хэрчмийг огтолдог.

Хаантанд зураг дээр хэчнээн ялгаатай шар шувуу байгааг тоолоход тусална уу.

Оролт

Эхний мөрөнд $n ,m (1\le n\le 3·10^5, 2\le m\le 1500)$ 4 тоонууд өгөгдөнө.

Дараагийн $n$ ширхэг мөр бүр хэрчим бүрийн үзүүүрийн цэгүүдийн координатыг илэрхийлэх $x_1, y_1, x_2, y_2$ тоонууд өгөгдөнө.

Дараагийн $m$ мөр бүр тус бүрт $x_i, y_i, r_i$ тоонууд өгөгдөх ба эдгээр нь $i$дэх тойргийн төв ба радиусыг илэрхийлнэ. Координат бүр абсолют утгаараа $10^4$-с хэтрэхгүй бүхэл тоо байна.Радиус нь $10^4$-с хэтрэхгүй эерэг бүхэл тоо байна.

Бүх тойрог ба хэрчмүүд ялгаатай байна.

Гаралт

Бодлогын хариу болох ганц тоог хэвлэнэ.

Жич: С++ хэл хэрэглэж байгаа бол 64-бит бүхэл тоог уншихдаа %lld тодорхойлогчийг ашиглахгүй байхыг зөвлөж байна. cin, cout стриймүүд эсвэл %I64d тодорхойлогчийг ашиглана уу.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
1 2
3 2 3 -2
0 0 2
6 0 2
Гаралт
1
Оролт
3 2
0 0 0 1
0 -1 0 1
0 -1 0 0
2 0 1
-2 0 1
Гаралт
3
Оролт
1 2
-1 0 1 0
-100 0 1
100 0 1
Гаралт
0

Тэмдэглэл

Here's an owl from the first sample. The owl is sitting and waiting for you to count it.

Сэтгэгдлүүдийг ачааллаж байна...