Masala D

"Xirtam"deb nomlanuvchi bir o'lkada N ta suv omborlari bor. Sirli sabablarga ko'ra M ta bir tomonli ariqlar bor. Sizda ushubu ariqlarni ko'rsatuvchi xarita bor, unda siz M ta u, v, w ko'rinishidagi qiymatlar berilgan, bunda 1 kunda u suv omboridan undagi w% hajmiga teng suv ariq orqali v suv omboriga oqib o'tadi.

Sizga a massiv berilgan bo'lib, 1<=i<=N uchun a[i] i-suv omboradiga suv hajmini anglatadi.

Ushbu o'lka xalqi sizdan K kundan so'ng har bir suv omborida qancha hajmdagi suv qolishini so'rashdi

K juda katta son bo'lgani tufayli w% = w/100 ni w * inv(100) mod 998244353 qilib ishlang

bunda a mod b a ni b ga bo'lgandagi qoldiqni anglatadi

inv(a) mod b = aᵇ⁻² mod b qachonki b tub son bo'lsa

Birinchi qatorda uchta son N, M, K beriladi

Ikkinchi qatorda N ta sondan iborat a massivi beriladi

Keyingi M ta qatorda 3 tadan son u, v, w lar beriladi

2<=N<=70

1<=M<=N*(N-1)/2

1<=K<=1e15

1<=i<=N uchun 0<=a[i]<=1e8

1<=u,v<=N

u, v, w da har bir u uchun barcha w lar yig'indisi 100dan oshmasligi kafolatlanadi

Subtask 1 - 10 ball: Barcha v=1 va K<=1000
Subtask 2 - 25 ball: Barcha v=1
Subtask 3 - 25 ball:  N<=20 va K<=1e5
Subtask 4 - 40 ball: chegaralar yoʻq

Bir qatorda N ta son chiqaring

1<=i<=N da i-son i-suv omborida K kundan so'ng qancha hajimdagi suv bo'lishini chiqaring

Javoblaringizni mod 998244353 da chiqaring