Кольорові обмеження

Вхідні дані

У першому рядку задано три цілі числа $n$, $m$ та $k$ (1 \leq n \leq 2 \cdot 10^5, 0 \leq m \leq 2 \cdot 10^5, 1 \leq k \leq 2 \cdot 10^5) — кількість вершин, ребер і кольорів.

У другому рядку задано двійковий рядок $a$ довжини $n$, де a_i — початковий біт вершини $i$.

У третьому рядку задано $n$ цілих чисел w_1,w_2,\ldots,w_n (0 \leq w_i \leq 10^9) — вартості зміни бітів.

У кожному з наступних $m$ рядків задано чотири цілі числа $u$, $v$, $b$ та $c$ (1 \leq u,v \leq n, b \in \{0,1\}, 1 \leq c \leq k). Це означає, що між вершинами $u$ та $v$ є ребро кольору $c$, яке задає вимогу x_u \oplus x_v=b.

У графі можуть бути кратні ребра та петлі. Деякі кольори можуть не зустрічатися серед ребер.

Вихідні дані

Виведіть $k$ цілих чисел.

Число на позиції $c$ має дорівнювати мінімальній вартості після видалення всіх ребер кольору $c$, або $-1$, якщо виконати всі вимоги неможливо.

Приклади

Примітка

У першому прикладі після видалення ребер кольорів $1$, $2$ та $3$ можна вибрати кінцеві біти 100, 110 та 000 відповідно. Мінімальні вартості змін дорівнюють 5+2=7, $5$ та $2$.

У другому прикладі після видалення кольору $1$ залишаються два однакові обмеження x_1=x_2. Достатньо змінити біт першої вершини за вартість $4$. Після видалення кольору $2$ або відсутнього в графі кольору $3$ залишається петля з вимогою x_1 \oplus x_1=1, яку неможливо виконати.

У третьому прикладі ребер немає. Для кожного кольору можна залишити всі початкові біти без змін, тому обидві відповіді дорівнюють $0$.

Оцінювання

1. $20$ балів — k=1.

2. $40$ балів — n \leq 16, m \leq 30, k \leq 10.

3. $60$ балів — n,m,k \leq 2000.

4. $80$ балів — k \leq 20.

5. $80$ балів — для всіх ребер b=0.

6. $100$ балів — для всіх вершин w_i=0.

7. $120$ балів — без додаткових обмежень.