Hearthstone

Hearthstone은 인기 있는 비디오 게임 중 하나이다. 다음 규칙을 주의 깊게 읽으시오. 일반적인 규칙과 다릅니다.

비밀 카드는 번호 $1$, $2$, $\ldots$, $n$으로 구분되는 $n$종류가 있다. 비밀과 관련된 이벤트는 두 종류이다.

• add: 번호를 알 수 없는 비밀 하나를 영웅 영역에 추가한다. 같은 번호의 비밀 두 개가 영웅 영역에 동시에 있을 수 없다.
• test $x$ $y$: 비밀 $x$가 존재하는지 검사한다. 비밀 $x$가 존재하면 $y=1$이고 비밀 $x$를 영웅 영역에서 제거한다. 그렇지 않으면 $y=0$이다. $y$의 값과 관계없이 test 이후에는 비밀 $x$가 영웅 영역에 없다.

이벤트 수열 $E = [e_1, \ldots, e_m]$이 유효한 것은, 각 add 이벤트에 $1$부터 $n$까지의 번호를 대응시켜서 이벤트 $e_1, e_2, \ldots, e_m$을 순서대로 수행할 수 있고, 그 과정에서 다음 조건이 모두 성립할 때이다.

• 처음에는 영웅 영역에 비밀이 없다.
• 비밀 $x$를 추가하는 add 이벤트 직전에는 비밀 $x$가 존재하지 않는다.
• test $x$ $1$ 직전에는 비밀 $x$가 존재한다.
• test $x$ $0$ 직전에는 비밀 $x$가 존재하지 않는다.

이벤트 $e_1, e_2, \ldots, e_q$가 주어진다. 처음에 $E$는 비어 있다. $i = 1, 2, \ldots, q$ 순서대로 $e_i$를 $E$의 끝에 추가하려고 한다. $E$가 유효하지 않으면 $e_i$를 제거하고 bug를 보고한다. 유효하면 $E$의 이벤트를 순서대로 수행한 뒤 영웅 영역에 반드시 있어야 하는 비밀의 수와 반드시 없어야 하는 비밀의 수를 구한다.

반드시 있거나 반드시 없는 비밀의 수는 단순히 있거나 없는 비밀의 수와 다르다. 예를 들어 $n = 2$이고 처음에 비밀 1과 2가 모두 없다면 답은 $0$과 $2$이다. add를 한 번 한 뒤에는 비밀 1과 2가 모두 불명이므로(있을 수도 없을 수도 있으므로) 답은 $0$과 $0$이다. test $2$ $0$을 한 뒤에는 비밀 2가 없으므로 추가된 비밀은 1임을 알 수 있다. 따라서 비밀 1이 있고, 답은 $1$과 $1$이다.

테스트 케이스가 여러 개 입력된다. 첫 줄에 테스트 케이스의 수 $T$ ($1\le T\le 10^5$)가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 비밀 카드의 종류 수 $n$과 이벤트 수 $q$ ($1 \le n, q \le 10^5$)가 주어진다.

이어지는 $q$개의 줄 중 $i$번째 줄은 $e_i$를 나타내며, 문자열 add이거나, 문자열 test와 정수 $x$, $y$ ($1 \le x \le n$, $0 \le y \le 1$)이다.

모든 테스트 케이스에 걸친 $n$의 합과 $q$의 합은 각각 $10^5$를 넘지 않는다.

각 테스트 케이스에 대해, 각 이벤트마다 추가할 수 있으면 영웅 영역에 반드시 있는 비밀의 수와 반드시 없는 비밀의 수를 두 정수로 출력한다. 추가할 수 없으면 bug를 출력한다.