트리 방문

높이가 $N$인 포화 이진 트리가 하나 있다. 즉 노드는 모두 $2^{N+1}-1$개이고, 깊이 $N$인 리프 노드는 $2^N$개다.

길이가 $N$인 이진수 $X$로 트리를 따라 내려간다. $X$의 가장 왼쪽 비트부터 차례대로 보면서 비트가 0이면 왼쪽 자식으로, 1이면 오른쪽 자식으로 내려간다. 예를 들어 $N = 2$일 때 $X = 0 = 00_2$이면 가장 왼쪽 리프 노드까지 내려가고, $X = 3 = 11_2$이면 가장 오른쪽 리프 노드까지 내려간다. $X = 2 = 10_2$이면 루트에서 오른쪽 자식으로 내려간 다음 왼쪽 자식으로 내려간다.

가장 처음에 $X = 0$이고, 루트만 방문한 상태다. 다음 두 쿼리를 처리하는 프로그램을 작성하시오.

• 1 C: $X$를 $(X + 2^C) \bmod 2^N$으로 바꾼다. 그 다음 바뀐 $X$로 루트에서부터 내려가면서 지나가는 노드를 모두 방문한다. 루트와 도착한 리프 노드도 방문한 노드에 포함된다.
• 2: 지금까지 방문한 서로 다른 노드의 개수를 출력한다. 같은 노드를 여러 번 방문해도 한 번만 센다.

첫째 줄에 트리의 높이 $N$과 쿼리의 개수 $Q$가 주어진다. ($1 \le N, Q \le 10^5$)

둘째 줄부터 $Q$개의 줄에 쿼리가 한 줄에 하나씩 주어진다. 1번 쿼리는 1 C 꼴이고 $0 \le C < N$이다. 2번 쿼리는 2 한 글자로 주어지고, 적어도 하나 주어진다.

2번 쿼리마다 방문한 서로 다른 노드의 개수를 한 줄에 하나씩 출력한다.