Sakurako et une Légende Volée#412

Sakurako et une Légende Volée

Inventer des légendes qui satisfont tous les participants de l'UJGOI est une tâche énorme.

C'est pourquoi cette légende a été volée.

Vous disposez d'un graphe dirigé avec sommets qui est initialement vide. À partir de la première seconde, pendant chaque seconde, une arête dirigée est ajoutée à ce graphe.

Votre tâche est de traiter requêtes.

Chaque requête est donnée par deux nombres et . Votre tâche est de déterminer le premier moment où il existe un chemin de à et de à .

Si même après que toutes les arêtes aient été ajoutées, il n'y a pas de chemin de à ou de à , vous devez afficher .

De plus, si x=y, vous devez afficher .

Input

La première ligne contient quatre entiers n,m,q,t (1\le n,m,q\le 3\cdot 10^5; t \in \{0,1\}).

Chacune des lignes suivantes contient deux entiers v_i et u_i (1 \leq v_i, u_i \leq n) — les arêtes qui sont ajoutées à un graphe initialement vide dans l'ordre où elles sont ajoutées.

Chacune des lignes suivantes contient deux entiers et (1\le x, y \le n), qui désignent une requête.

Lorsque t=0, chaque requête est donnée sans encodage.

Lorsque t=1, chaque requête est donnée avec encodage :

  1. initialement, key=0. Lorsque vous recevez les entiers dans une requête, vous formez les entiers ;

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

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

  4. après cela, vous répondez à la requête ; laissez être la réponse à cette requête, puis vous mettez à jour key = ans avant de répondre à la prochaine requête.

Output

Pour chaque requête, affichez la réponse.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Le graphe pour les deux exemples. Chaque arête a une étiquette qui indique le moment où elle a été ajoutée. Notez que le deuxième exemple est crypté ; après une description correcte, vous vous retrouvez avec les mêmes requêtes que dans le premier cas de test.

Pour les nœuds , il n'est pas difficile de voir que seulement lorsque toutes les arêtes jusqu'à la 6^{ème} sont présentes, il existe un chemin de à et de à .

Pour les nœuds , même lorsque toutes les arêtes sont présentes, il n'y a pas de chemin de à .

Pour les nœuds , seulement lorsque toutes les arêtes sont présentes, il existe un chemin de à et de à .

Pour les nœuds , même lorsque toutes les arêtes sont présentes, il n'y a pas de chemin de à .

Pour les nœuds , seulement lorsque toutes les arêtes sont présentes, il existe un chemin de à et de à .

Scoring

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

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

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

  4. ( points) : t = 0 ;

  5. ( points) : sans contraintes supplémentaires.