Rocket Launcher

level: 80/100

nama file: rocket.pas

Deskripsi

Gawat! Bumi diserang alien dari galaksi Andromeda! Alien-alien tersebut telah berhasil menduduki beberapa daerah. Alien-alien tersebut telah membangun M buah markas besar di bumi, yang letaknya dapat dianggap berada di atas sebuah bidang kotak-kotak. Setiap markas tersebut berbentuk segi empat dengan ujung kiri-bawah pada kotak (x1,y1) dan ujung kanan-atas pada kotak (x2,y2). Untungnya, para ilmuwan dari penjuru dunia telah berhasil bekerja sama untuk membuat roket tercanggih untuk menghancurkan markas-markas kekuasaan alien di bumi. Jika seluruh markas alien di bumi berhasil dimusnahkan, niscaya mereka akan mundur dan pergi dari bumi.

Ada T jenis roket yang dapat ditembakkan, masing-masing mempunyai jarak tempuh maksimal sebesar L, dan radius ledak sebesar R. Radius ledak adalah besar area yang akan dihancurkan roket, misalnya jika sebuah roket dengan radius ledak 10 ditembakkan, maka jarak 10 kotak atau kurang di sekitar titik jatuh roket tersebut akan dihancurkan juga oleh roket. Setiap roket tersebut menggunakan antiproton sebagai hulu ledaknya, masing-masing sebanyak G.

Sayangnya biaya pembuatan antiproton, hulu ledak roket-roket tersebut, sangatlah mahal. Karena itulah Dewan Keamanan PBB meminta anda, ilmuwan komputer terjenius sedunia, untuk menentukan roket-roket apa saja dan kemana harus ditembakkan agar seluruh markas dapat dimusnahkan dengan biaya seminimal mungkin, dalam hal ini menggunakan antiproton sesedikit mungkin. Namun berhati-hatilah, karena ada beberapa markas alien yang letaknya dekat dengan pemukiman penduduk. Penduduk pemukiman tersebut sulit untuk diungsikan karena kerusakan infrastruktur, padahal markas alien harus segera dihancurkan. Karena itulah roket harus ditembakkan dan tidak boleh mengenai pemukiman penduduk. Ada P buah pemukiman, masing-masing berbentuk segi empat dengan ujung kiri-bawah pada (i1,j1) dan ujung kanan-atas pada (i2,j2).

Catatan: tempat peluncuran roket anda terletak pada kotak (0,0).

Masukan

Baris pertama terdiri dari tiga bilangan M (0 < M < 1000), P (0 < P < 1000) dan T (0 < T < 100) yang masing-masing merupakan jumlah markas alien, pemukiman dan jenis roket.

M baris berikutnya masukan terdiri dari 4 bilangan x1, y1, x2 dan y2 (-1000000 < x1 < x2 < 1000000, -1000000 < y1 < y2 < 1000000) yang merupakan koordinat kiri-bawah dan kanan-atas tiap markas alien.

P baris berikutnya masukan terdiri dari 4 bilangan i1, j1, i2 dan j2 (-1000000 <i1 <i2 < 1000000, -1000000 < j1 < j2 < 1000000) yang merupakan koordinat kiri-atas dan kanan-bawah tiap pemukiman. T baris berikutnya masukan terdiri dari 3 bilangan yaitu L(1 < L < 2000000), R(0 < R < 100000) dan G(1 < G < 100) yang masing-masing adalah jarak tempuh maksimal, radius ledak dan jumlah antiproton dari tiap roket.

Keluaran

Keluaran terdiri dari beberapa baris, setiap baris terdiri dari sebuah bilangan q yang merupakan tipe roket yang ditembakkan, dan dua bilangan x dan y yang merupakan koordinat titik jatuh roket q. Keluaran diurutkan dari tipe roket, kemudian dari koordinat-x dan terakhir dari koordinat-y.

Contoh

input

4 1 2

10 10 10 10

7 7 8 8

6 6 6 6

1 1 4 4

9 9

10 1 1

10 3 3
output

1 10 10

2 2 2

2 7 7