F. Всем чмоки в этом чатике

В соцсети $n$ пользователей, каждый в начале дня сидит в своём чате один. Происходят события трёх видов: участник пишет сообщение всем в своём чате (включая себя), два чата сливаются, участник спрашивает, сколько сообщений он не прочитал, и читает их.

Номера участников зашифрованы переменной zerg, которая меняется после каждого события, — значит обработать события заранее и оптом не выйдет, только по одному и по порядку.

В первой строке $n$ и $m$ ($1 \le n \le 10^5$, $1 \le m \le 3 \cdot 10^5$). В каждой из следующих $m$ строк — тип события $t$ и его аргументы.

Переменная $zerg$ в начале дня равна нулю, $p = 10^6 + 3$.

• 1 i ($0 \le i < n$): участник $(i + zerg) \bmod n$ пишет сообщение всем в своём чате, включая себя; затем $zerg \leftarrow (30 \cdot zerg + 239) \bmod p$.
• 2 i j ($0 \le i, j < n$): участники $(i + zerg) \bmod n$ и $(j + zerg) \bmod n$. Если они в одном чате, не происходит ничего. Иначе чаты сливаются и $zerg \leftarrow (13 \cdot zerg + 11) \bmod p$.
• 3 i ($0 \le i < n$): участник $(i + zerg) \bmod n$ узнаёт число непрочитанных $q$ и читает их; затем $zerg \leftarrow (100500 \cdot zerg + q) \bmod p$.

Для каждого события третьего типа выведите число непрочитанных сообщений в отдельной строке.