Sakurako və Oğurlanmış Əfsanə#412

Sakurako və Oğurlanmış Əfsanə

Bütün UJGOI iştirakçılarını razı salan şərtlər düşünmək böyük bir işdir.

Buna görə də bu şərt oğurlanıb.

Sizə düyünü (node) olan istiqamətlənmiş qraf verilir. Bu qraf əvvəlcə boşdur. İlk saniyədən başlayaraq, saniyə ərzində hər saniyədə bu qrafa bir ədəd istiqamətlənmiş əlaqə (edge) əlavə edilir.

Sizin tapşırığınız sorğuya cavab verməkdir.

Hər bir sorğu iki ədəd ( və ) ilə verilir. Sizin tapşırığınız -dən -ə və -dən -ə gedən bir yolun mövcud olduğu ilk anı müəyyən etməkdir.

Əgər bütün əlaqə əlavə edildikdən sonra belə, -dən -ə və ya -dən -ə gedən yol yoxdursa, çap etməlisiniz.

Həmçinin, əgər x=y olarsa, çap etməlisiniz.

Input

Birinci sətirdə dörd tam ədəd n,m,q,t (1\le n,m,q\le 3\cdot 10^5; t \in \{0,1\}) verilir.

Sonrakı sətrin hər birində iki tam ədəd v_i və u_i (1 \leq v_i, u_i \leq n) — başlanğıcda boş olan qrafa əlavə edilən əlaqələr (əlavə edildiyi sırayla) verilir.

Sonrakı sətrin hər biri iki tam ədəd və (1\le x, y \le n) ehtiva edir ki, bu da bir sorğunu göstərir.

t=0 olduqda, hər bir sorğu kodlaşdırılmadan verilir.

t=1 olduqda, hər bir sorğu kodlaşdırılmış şəkildə verilir:

  1. başlanğıcda, key=0-dır. Sorğuda ədədləri verildikdə, ədədlərini formalaşdırırsınız;

  2. x=(key-1 + a) \mod n+1;

  3. y=(key-1 + b) \mod n+1;

  4. bundan sonra, sorğunu cavablandırırsınız; bu sorğu üçün cavab olsun, onda növbəti sorğunu cavablandırmazdan əvvəl key = ans ilə yeniləyirsiniz.

Output

Hər bir sorğu üçün cavabı çap edin.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Hər iki nümunə üçün qraf. Hər bir əlaqənin əlavə edildiyi zamanı göstərən etiket var. İkinci nümunənin şifrələndiyini unutmayın; düzgün deşifrədən sonra, birinci nümunədəki ilə eyni sorğular alınır.

düyünləri üçün yalnız 6-cı əlaqəyə qədər bütün əlaqələr mövcud olduqda -dən -ə və -dən -yə gedən yolun olduğunu görmək çətin deyil.

düyünləri üçün bütün əlaqələr mövcud olsa belə, -dən -ə gedən yol yoxdur.

düyünləri üçün yalnız bütün əlaqələr mövcud olduqda -dən -ya və -dan -yə gedən yol var.

düyünləri üçün bütün əlaqələr mövcud olsa belə, -dən -ə gedən yol yoxdur.

düyünləri üçün yalnız bütün əlaqələr mövcud olduqda -dən -yə və -dən -ə gedən yol var.

Scoring

  1. ( bal): n,m\le 80, t = 0;

  2. ( bal): n,m\le 10^3, t = 0;

  3. ( bal): q \le 100, t = 0;

  4. ( bal): t = 0;

  5. ( bal): əlavə məhdudiyyətlər olmadan.