Первая строка содержит два целых числа $n$ и $m$ ($1\leq n\leq 21$, $n-1\leq m\leq\frac{n(n-1)}{2}$).

Затем следуют $m$ строк, каждая из которых содержит четыре целых числа $u$, $v$, $p$ и $q$ ($1\leq u\neq v\leq n$, $1\leq p<q<998\,244\,353$, $\gcd(p,q)=1$) — существует неориентированное ребро между вершинами $u$ и $v$, и оно каждый день появляется с вероятностью $\frac{p}{q}$.

Гарантируется, что в графе нет петель или кратных рёбер и что граф связен, если все рёбра появились.

Дополнительное ограничение на входные данные: Пусть $g_{i,j}$ — вероятность появления ребра между вершинами $i$ и $j$ ($g_{i,j}=0$, если между $i$ и $j$ нет ребра). Гарантируется, что для любого $S\subseteq\{1,2,\ldots,n\}$ ($|S|\ge 1$), $$\prod_{i\in S}\left(\prod_{j\in\{1,2,\ldots,n\}\setminus S}(1-g_{i,j})\right)\not\equiv1\pmod{998\,244\,353}.$$