문제 107
큐의 함수 합성
함수를 저장하는 빈 큐가 있다. 다음 $Q$개의 쿼리를 순서대로 처리해 보자.
- $0\ a\ b$: 두 정수 $a$, $b$로 정의되는 함수 $f(x)=ax+b$를 큐의 맨 뒤에 넣는다.
- $1$: 큐의 맨 앞 함수를 제거한다. 이때 큐는 비어 있지 않다.
- $2\ x$: 입력값 $x$에 큐의 함수를 앞에서부터 차례대로 적용한 결과를 $998\,244\,353$으로 나눈 나머지를 구한다.
큐에 함수 $f_1$, $f_2$, $f_3$이 이 순서로 들어 있다면 $2$번 쿼리는 $f_3(f_2(f_1(x)))$를 계산한다. 큐가 비어 있으면 결과는 $x$이다. $998\,244\,353$은 소수이다.
입력
첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 200\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 본문에서 설명한 형식의 쿼리가 주어진다. 각 쿼리의 정수는 공백으로 구분되어 주어진다. $(0 \le a, b, x < 998\,244\,353)$
출력
$2$번 쿼리의 답을 쿼리가 주어진 순서대로 한 줄에 하나씩 출력한다.
예제 입력 1
11 2 7 0 2 3 0 4 5 2 1 1 2 1 0 0 9 2 123 1 1 2 10
예제 출력 1
7 25 9 9 10