Dairələr
Təyyarədə N dairə verilib və sizdən Q sorğuya cavab verməyiniz tələb olunur. Hər bir i-ci sorğu üçün, əvvəlcə t_i nömrəli dairənin ən azı bir ortaq nöqtəsi olan digər dairələrin sayını tapmalısınız. Daha sonra, t_i dairəsini təyyarədə yeni bir mövqeyə köçürməlisiniz. Burada dairə dedikdə, həm çevrə, həm də onun daxilindəki bütün nöqtələr nəzərdə tutulur.
seed_k=(31 313 131 * seed_{k-1} + 13 131 313) mod 1 000 000 007
Lazımi məlumatların növbəti dəyərini əldə etmək üçün {seed_k} ardıcıllığının növbəti elementini götürməlisiniz. Bu əməliyyatı nextint() kimi qeyd edək.
Məlumatlar aşağıdakı qaydada yaradılır:
Burada x_i və y_i - i-ci dairənin başlanğıc koordinatları, r_i - i-ci dairənin radiusudur. t_j - j-ci sorğuda maraq doğuran dairənin nömrəsidir. new_x_j və new_y_j - j-ci sorğudan sonra t_j dairəsinin alacağı yeni mərkəz koordinatlarıdır. Dairələr yaradılma sırasına görə 1-dən başlayaraq nömrələnir.
Giriş verilənləri
Üç tam ədəd: N, Q və seed_0 (1 ≤ N ≤ 1000000, 1 ≤ Q ≤ 100000, 0 ≤ seed_0 ≤ 1000000006) - dairələrin sayı, sorğuların sayı və təsadüfi ədədlər ardıcıllığının sıfırıncı elementi. Qeyd edək ki, yaradılma birinci elementdən başlayır, yəni, x_{1 }= seed_1 mod 1000000.
Çıxış verilənləri
Q sətir. Hər bir i-ci sətir bir tam ədəd içərməlidir - i-ci sorğunun icrası zamanı t_i nömrəli dairənin kəsişdiyi dairələrin sayı. Qeyd edək ki, əvvəlcə sorğuya cavab tapılmalı, sonra dairə yeni mövqeyə köçürülməlidir. Sorğular zamanı dairələrin radiusları dəyişmir. Dairələrin mövqeyinin dəyişməsi növbəti sorğulara təsir edir, yəni, hər növbəti sorğu əvvəlki bütün köçürmələr nəzərə alınaraq icra olunur.