Universal Cup Judging System

Universal Cup

Limite de temps : 2.5 s Limite de mémoire : 1024 MB Points totaux : 100 Difficulté: [afficher] Hackable ✓
Statistiques

Дано неорієнтований граф із $n$ вершинами, який спочатку не має ребер. Обробіть $q$ операцій таких двох типів:

  • $+\ u\ v\ w$: Додати ребро, що з'єднує вершини $u$ і $v$, з вагою $w$.
  • $?\ u\ v$: Визначимо вагу шляху як побітове І (bitwise-and) ваг усіх ребер на цьому шляху. Обчисліть найбільшу можливу вагу шляху, що починається у вершині $u$ і закінчується у вершині $v$. Якщо шляху між вершинами $u$ і $v$ не існує, відповіддю має бути $-1$.

Вхідні дані

Є декілька наборів вхідних даних. Перший рядок вхідних даних містить ціле число $T$ ($1 \le T \le 100$) — кількість наборів вхідних даних. Для кожного набору вхідних даних:

Перший рядок містить два цілі числа $n$ і $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) — кількість вершин і кількість операцій.

У наступних $q$ рядках $i$-й рядок спочатку містить символ $op$ ($op \in \{+, ?\}$), що вказує на тип $i$-го запиту.

  • Якщо $op = +$, то далі йдуть три цілі числа $u$, $v$ і $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), що позначають операцію першого типу.
  • Якщо $op = ?$, то далі йдуть два цілі числа $u$ і $v$ ($1 \le u, v \le n$, $u \ne v$), що позначають операцію другого типу.

Гарантується, що в кожному наборі вхідних даних є принаймні одна операція другого типу. Також сума $n$ за всіма наборами вхідних даних не перевищує $10^3$, а сума $q$ за всіма наборами вхідних даних не перевищує $10^6$.

Вихідні дані

Щоб зменшити розмір виводу, для кожного набору вхідних даних виведіть лише один рядок, що містить одне ціле число — суму відповідей на всі операції другого типу.

Приклади

2
4 11
+ 1 3 6
+ 3 4 2
? 1 4
+ 1 4 3
? 4 1
+ 4 3 4
? 1 4
+ 3 2 3
? 1 2
+ 1 1 4
? 1 3
4 4
+ 1 2 64
+ 3 4 32
? 1 2
? 3 1
17
63

Примітка

Для першого прикладу відповіді на операції другого типу дорівнюють $2$, $3$, $4$, $2$ та $6$.

Для другого прикладу відповіді на операції другого типу дорівнюють $64$ та $-1$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.