K-ekvivalentlik
Müsbət tam ədədlər çoxluğu K üzərində düşünün.
p və q sıfırdan fərqli iki onluq rəqəm olsun. Əgər aşağıdakı şərt yerinə yetirilirsə, bu rəqəmləri K-ekvivalent adlandırırıq:
Hər bir n üçün, əgər n-in onluq yazılışında bir rəqəm p ilə q və ya q ilə p əvəz edilərsə, alınan ədəd K-nin elementi olmalıdır.
Məsələn, əgər K 3-ə bölünən tam ədədlər çoxluğudursa, 1, 4 və 7 rəqəmləri K-ekvivalentdir. Çünki bir ədədin onluq yazılışında 1-i 4 ilə əvəz etmək onun 3-ə bölünməsini dəyişdirmir.
K-ekvivalentlik bir ekvivalentlik münasibətidir (refleksiv, simmetrik və tranzitivdir).
Sizə müsbət tam ədədlərin birləşməsindən ibarət sonlu K çoxluğu verilir.
Vəzifəniz 1-dən 9-a qədər olan rəqəmlərin ekvivalentlik siniflərini tapmaqdır.
Giriş verilənləri
Birinci sətir K çoxluğunu təşkil edən intervalların sayı olan n ədədini ehtiva edir (1 ≤ n ≤ 10 000). Növbəti n sətirin hər biri a_i və b_i müsbət tam ədədlərini ehtiva edir ki, bu da [a_i, b_i] intervalını təsvir edir (yəni, a_i və b_i arasında olan müsbət tam ədədlər çoxluğu, daxil olmaqla), burada 1 ≤ a_i ≤ b_i ≤ 10^18. Həmçinin, i [2..n]: a_i ≥ b_i-1 + 2.
Çıxış verilənləri
Hər bir ekvivalentlik sinfini onun elementlərinin artan qaydada birləşməsi kimi təqdim edin.
1-dən 9-a qədər olan rəqəmlərin bütün ekvivalentlik siniflərini leksikoqrafik qaydada, hər sətirdə birini çıxış edin.