Məktəb yazışmaları

Loсяş, Smeshariklər üçün təhsili daha əlçatan etmək məqsədilə bir məktəb açdı. Bu məktəbdə, digər məktəblərdə olduğu kimi, müəllimlər (məsələn, Pin və Sovunya) və şagirdlər (məsələn, Kroş və Yojik) var. Loсяş isə məktəbin direktorudur. Məktəbdə ümumilikdə n Smesharik (müəllimlər və şagirdlər) var. Onları 1-dən n-ə qədər nömrələyək.

Şagirdlər və müəllimlər arasında ünsiyyət üçün bir messencer yaradılıb. Bu messencer hər hansı bir istifadəçiyə mesaj göndərməyə imkan verir, lakin bəzi əlavə qaydalarla:

• Əgər şagird müəllimə mesaj göndərirsə, bu mesajın surəti bütün müəllim heyətinə göndərilir. Yəni, direktor və bütün müəllimlər bu mesajı alır.

• Əgər müəllim şagirdə mesaj göndərirsə, mesajı həmin şagird və direktor alır.

• İstifadəçiyə mesaj gəldikdə, o, oxunmamış mesajlar siyahısına düşür.

• Müəllim şagird tərəfindən göndərilən oxunmamış mesajı oxuduqda, bu mesaj bütün müəllimlərin oxunmamış siyahısından silinir, lakin direktorun siyahısından yox.

• Digər hallarda, istifadəçi aldığı oxunmamış mesajı oxuduqda, o, yalnız onun oxunmamış siyahısından silinir.

Qeyd edək ki, direktor şagird tərəfindən göndərilən oxunmamış mesajı oxuduqda, o, yalnız onun oxunmamış siyahısından silinir (müəllimlərin siyahısından yox).

Loсяş tədris prosesini optimallaşdırmaq istəyir və müəyyən vaxtlarda onu maraqlandırır ki, müəyyən bir istifadəçinin neçə oxunmamış mesajı var.

Sizə hadisələrin baş verdiyi ardıcıllıqla q hadisə verilir. Loсяşın sualına uyğun olaraq hər bir hadisə üçün cavabı verin.

Giriş məlumatları

Birinci sətirdə iki tam ədəd n və q (1 ≤ n, q ≤ 2 * 10^5) - məktəbdəki Smeshariklərin sayı və hadisələrin sayı verilir.

İkinci sətirdə n tam ədəd t[i] (t[i] ∈ 0, 1, 2) - Smeshariklərin rolları verilir. Əgər t[i] = 0, onda i-ci Smesharik - direktor Loсяşdır. Əgər t[i] = 1 - müəllimdir. Əks halda - şagirddir. t[i] arasında yalnız bir ədədin 0 olduğu təmin edilir.

Növbəti q (1 ≤ i ≤ q) sətirdə hadisələrin təsviri verilir. i nömrəli hadisə üç növdən birinə malik ola bilər:

• "1 a[i] b[i]" - istifadəçi a[i] istifadəçi b[i]-yə mesaj göndərdi (1 ≤ a[i], b[i] ≤ n, a[i] ≠ b[i]).

• "2 a[i] x[i]" - istifadəçi a[i] hadisə nömrəsi x[i] zamanı göndərilən mesajı oxudu (1 ≤ a[i] ≤ n, 1 ≤ x[i] < i).

• "3 a[i]" - istifadəçi a[i]-nin neçə oxunmamış mesajı olduğunu göstərmək tələb olunur (1 ≤ a[i] ≤ n).

İkinci növ hadisələr üçün təmin edilir ki, x[i] nömrəli hadisə zamanı istifadəçi nömrəsi a[i]-yə oxunmamışa düşən mesaj göndərilib. Həmçinin, bu mesaj hələ də onun oxunmamışlarındadır.

Çıxış məlumatları

Üçüncü növ hadisələrin hər biri üçün yeni sətirdə istifadəçi a[i]-nin neçə oxunmamış mesajı olduğunu göstərin.