Սակուրակո և գողացված լեգենդ#412

Սակուրակո և գողացված լեգենդ

2 վայրկյան
256 մեգաբայթ
Hard

Լեգենդներ մտածելը, որոնք բավարարում են բոլոր UJGOI մասնակիցներին, բարդ գործ է:

Այդ պատճառով այս լեգենդը գողացվեց:

Դուք ստանում եք ուղղորդված գրաֆ, որի մեջ գագաթներ կան, որը սկզբում դատարկ է: Առաջին վայրկյանից սկսած, յուրաքանչյուր վայրկյան, այս գրաֆին ավելացվում է ուղղորդված կող:

Ձեր առաջադրանքն է մշակել հարցում:

Յուրաքանչյուր հարցման մեջ տրվում է երկու թիվ և : Ձեր առաջադրանքն է որոշել ժամանակի առաջին պահը, երբ -ից -ին և -ից -ին անցնելու ճանապարհ կա:

Եթե նույնիսկ բոլոր կողերը ավելացվելուց հետո -ից -ին կամ -ից -ին ճանապարհ չկա, դուք պետք է արտածեք :

Նաև, եթե x=y, դուք պետք է արտածեք :

Input

Առաջին տողում տրված են չորս ամբողջ թվեր՝ n,m,q,t (1\le n,m,q\le 3\cdot 10^5; t \in \{0,1\}):

Հաջորդ տողերից յուրաքանչյուրը պարունակում է երկու ամբողջ թիվ՝ v_i և u_i (1 \leq v_i, u_i \leq n) — կողերը, որոնք ավելացվում են սկզբում դատարկ գրաֆում այն կարգով, որով դրանք ավելացվում են:

Հաջորդ տողերից յուրաքանչյուրը պարունակում է երկու ամբողջ թիվ՝ և (1\le x, y \le n), որոնք նշում են հարցումը:

Երբ t=0, յուրաքանչյուր հարցում տրվում է առանց կոդավորման:

Երբ t=1, յուրաքանչյուր հարցում տրվում է կոդավորմամբ:

  1. սկզբում, key=0: Երբ հարցման մեջ ձեզ տրվում են ամբողջ թվեր , դուք ձևավորում եք ամբողջ թվեր ;

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

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

  4. դրանից հետո, դուք պատասխանեք հարցմանը; թող լինի այս հարցման պատասխան, ապա դուք թարմացնում եք key = ans հաջորդ հարցմանը պատասխանելուց առաջ:

Output

Յուրաքանչյուր հարցման համար, արտածեք պատասխանը:

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Գրաֆը երկու օրինակների համար: Յուրաքանչյուր կող ունի պիտակ, որը նշում է ժամանակի պահը, երբ այն ավելացվել է: Նշենք, որ երկրորդ օրինակը կոդավորված է; ճիշտ ապակոդավորումից հետո, դուք կստանաք նույն հարցումները, ինչ առաջին թեստի դեպքում:

Գագաթների համար դժվար չէ տեսնել, որ միայն երբ բոլոր կողերը մինչև 6-րդ առկա են, կա ճանապարհ -ից -ին և -ից -ին:

Գագաթների համար նույնիսկ երբ բոլոր կողերը առկա են, չկա ճանապարհ -ից :

Գագաթների համար միայն երբ բոլոր կողերը առկա են, կա ճանապարհ -ից -ին և -ից -ին:

Գագաթների համար նույնիսկ երբ բոլոր կողերը առկա են, չկա ճանապարհ -ից :

Գագաթների համար միայն երբ բոլոր կողերը առկա են, կա ճանապարհ -ից -ին և -ից -ին:

Scoring

  1. ( միավոր): n,m\le 80, t = 0;

  2. ( միավոր): n,m\le 10^3, t = 0;

  3. ( միավոր): q \le 100, t = 0;

  4. ( միավոր): t = 0;

  5. ( միավոր): առանց լրացուցիչ սահմանափակումների.