기체와 쿼리

원이는 변형되지 않는 직육면체 모양의 실험 기구를 가지고 있다.

원이는 이 실험 기구를 한 면에 평행한 단면으로 $N$등분하고, 각각의 인접한 칸을 구분하는 고체 칸막이를 $N-1$개 설치했다. 초기에 실험 기구는 진공 상태이다.

이제 원이는 칸 $N$개와 칸막이 $N-1$개에 대해 아래와 같은 작업을 반복해 수행할 것이다. 칸막이를 제거하더라도 칸의 번호는 바뀌지 않음에 유의하라.

• $1$ $X$ : $X$번 칸과 $X+1$번 칸 사이의 칸막이를 제거한다.
• $2$ $X$ : 번 칸과 번 칸 사이에 칸막이를 설치한다.

또한 다음을 가정하자.

• 칸막이는 기체에 의해 움직이지 않는다.
• 칸막이로 구분된 칸 사이로는 기체가 드나들 수 없으며, 그렇지 않은 칸 사이로는 자유롭게 이동할 수 있다.
• 칸막이로 구분되지 않은 두 개 이상의 칸이 있을 때, 연결된 칸 각각의 기체 양은 동일하다.

원이는 위 작업을 시뮬레이션할 놀라운 방법이 떠올랐으나, 시험 공부를 하느라 PS를 게을리 했기 때문에 구현을 할 줄은 모른다. 여러분이 원이를 도와 이 작업을 구현해 주자.

첫째 줄에 칸의 개수 $N$과 작업의 횟수 $Q$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 100~000$, $1 \leq Q \leq 100~000$)

4번 작업이 주어질 때마다 답을 아래와 같이 정수로 구한 뒤 한 줄에 하나씩 출력한다.

4번 작업의 답은 항상 유리수임을 증명할 수 있다. 4번 작업이 주어지면, 이 유리수가 기약분수로 $\frac P Q$라 할 때, $P \equiv R \times Q$ (mod )인 이상 미만의 정수 을 대신 구한다. 이러한 이 유일하게 존재하는 입력만 주어짐을 보장한다.

$998~244~353$은 소수이다.

이 문제를 해결하는 데 사용할 수 있는 페르마 소정리의 내용은 다음과 같다.

임의의 소수 $p$와 정수 $a$에 대해 항상 다음 식이 성립한다.

$a ^ {p-1} \equiv 1$ (mod )