IQ testi robotlar üçün
Lyoşa robotunu IQ testinə hazırlayır. 2116-cı ildə robotlar üçün IQ testi aşağıdakı şəkildə keçirilir. Robota n sətir və m sütundan ibarət düzbucaqlı bir cədvəl göstərilir, burada hər bir hüceyrə müəyyən bir rəngə boyanmışdır.
Daha sonra imtahançı robota q dəfə aşağıdakı tapşırığı yerinə yetirməyi xahiş edir. İmtahançı cədvəldə müəyyən bir hüceyrəni göstərir və robot cavab olaraq iki başqa hüceyrə seçməlidir. Bu zaman aşağıdakı şərtlər yerinə yetirilməlidir:
Robot tərəfindən seçilən hüceyrələrdən heç biri imtahançı tərəfindən göstərilən hüceyrə ilə üst-üstə düşməməlidir.
Seçilən hüceyrələrdən biri göstərilən hüceyrə ilə eyni sütunda, digəri isə eyni sətirdə olmalıdır.
Robot tərəfindən seçilən iki hüceyrənin rəngləri fərqli olmalıdır.
Seçilən hüceyrələr arasındakı məsafə minimal olmalıdır. Hüceyrələr arasındakı məsafə (
r[1],c[1]) və (r[2],c[2]) olaraq |r[1]-r[2]| + |c[1]-c[2]| kimi müəyyən edilir.
Bəzən, təsvir olunan şəkildə iki hüceyrə seçmək mümkün olmur, bu halda robot tapşırığa cavab olaraq bunu bildirməlidir.
Lyoşa robotunu tapşırığı mümkün qədər yaxşı yerinə yetirməyi öyrətmək istəyir. Ona robotu proqramlaşdırmağa kömək edin.
Giriş məlumatları
Birinci sətirdə cədvəldəki sətir və sütunların sayı olan tam ədədlər n və m verilir (2 ≤ n, m ≤ 500 000, n * m ≤ 10^6).
Növbəti n sətir hər biri m kiçik latın hərfi olan cədvəlin təsvirini ehtiva edir, bu sətirlərin i-ci sətirinin j-ci simvolu hüceyrənin rəngini (i, j) təyin edir. Eyni hərflər eyni rəngi, fərqli hərflər isə fərqli rəngi göstərir.
Növbəti sətirdə imtahançının suallarının sayı olan q ədədi verilir (1 ≤ q ≤ 200 000).
Növbəti q sətir sualların təsvirini ehtiva edir. Bu sətirlərin i-ci sətirində iki ədəd x[i] və y[i] verilir - cavab tapılmalı olan hüceyrənin kəsişdiyi sətir və sütunun nömrəsi (1 ≤ x[i] ≤ n, 1 ≤ y[i] ≤ m).
Çıxış məlumatları
Hər bir sual üçün cavabı ayrı bir sətirdə verin. Əgər bütün şərtlərə cavab verən hüceyrə cütlüyü tapmaq mümkün deyilsə, -1 çıxarın. Əks halda, seçilən iki hüceyrənin təsvirini verən dörd ədəd r[1], c[1], r[2], c[2] çıxarın. Əgər bir neçə optimal cavab varsa, istənilənini çıxarın.