Coffre électronique – Qualification 2022

Énoncé¶

Joseph Marchand s'est rendu compte que le coffre qu'il cherche à ouvrir est bien trop sécurisé pour qu'il puisse deviner la combinaison d'une façon aussi simple ! Cependant tout espoir n'est pas perdu, car il a réussi à modifier le circuit. Il a rajouté un certain nombre de cables électriques, et est capable de changer la valeur d'une puce à volonté.

Le coffre contient un circuit complexe, décrit sous la forme d'un ensemble de puces, reliées entre elles par des fils. Il existe au moins un chemin entre chaque paire de puces (depuis que Joesph à rajouté des fils, il peut y en avoir plusieurs). Chaque puce envoie un signal $s_i$ au verrou lorsqu'elle est activée. Joseph Marchand tente de passer outre la sécurité du coffre et a besoin de votre aide pour calculer rapidement les effets de ses manipulations.

Il veut régulièrement modifier la valeur $s_i$ contenue par une puce, puis mesurer l'effet que cela à sur le circuit en connectant les deux bornes d'un générateur électrique à deux puces $a$ et $b$ du circuit. Il se demande alors quel signal est envoyé au verrou du coffre suite à cette opération. Une puce $c$ est activée s'il existe un chemin de $a$ vers $b$ passant par $c$, qui ne repasse pas deux fois par le même fil (mais peut passer deux fois par la même puce). Le signal reçu par le verrou est alors le produit du signal envoyé par chaque puce activée, modulo $1671404011$ (car on ne peut pas représenter de trop grands nombres par un signal électrique).

Exemple¶

Ce circuit est l'état initial du circuit dans le premier exemple d'entrée. Les valeurs des puces 2, 3 et 5 vont cependant changer.

Entrée¶

L'entrée contiendra :

• Sur la première ligne, un entier : N, nombre de puces.
• Sur la ligne suivante, un entier : M, nombre de fils.
• Sur la ligne suivante, un entier : R, nombre de requêtes.
• Sur la ligne suivante, une liste de N entiers séparés par des espaces : signaux, liste des signaux.
• Sur les lignes suivantes, une liste de M éléments : fils, liste des fils entre les puces.
  • Une ligne par élément de la liste : séparés par des espaces, un entier puce1 (première extrémité du fil), et un entier puce2 (seconde extrémité du fil).
• Sur les lignes suivantes, une liste de R éléments : requetes, liste des requêtes.
  • Une ligne par élément de la liste : séparés par des espaces, un entier puce modifiee (puce dont la valeur est modifiée), un entier nouvelle valeur (nouvelle valeur de la puce), un entier puce a (première extrémité alimentée), et un entier puce b (seconde extrémité alimentée).

Sortie¶

Affiche le signal envoyé au coffre-fort pour chaque requête.

Contraintes¶

• $1 \le N \le 100\,000$
• $1 \le M \le 100\,000$
• $1 \le R \le 100\,000$
• $0 \le s_i \le 1\,671\,404\,011$
• $0 \le a_i, b_i, x_i, y_i < N$