시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 0 0 0 0.000%

문제

$N$개의 정점으로 이루어진 포레스트가 있다. 정점은 $1$부터 $N$까지 번호가 매겨져 있으며, 간선은 없다. 모든 정점 $v$는 정수 $X_v$를 가지고 있고, 초기값은 $X_v = 1$이다.

아래의 쿼리를 수행하는 프로그램을 작성하시오.

  • 1 $a$ $b$ $c$: 정점 $a$와 $b$를 가중치가 $c$인 간선으로 연결한다. 쿼리의 수행 결과가 포레스트인 경우만 입력으로 주어진다.
  • 2 $a$ $b$: 정점 $a$와 $b$를 연결하는 간선을 제거한다. 두 정점 사이에 간선이 있는 경우만 입력으로 주어진다.
  • 3 $a$: $X_a$를 $1-X_a$로 변경한다. 그 다음 $a$가 포함된 트리에서 다음을 구한다.
    • 트리의 정점을 $v_1, v_2, \dots, v_k$라고 하자. 이때 $\min_{1 \le i \le k}{\left\{ \sum_{1 \le j \le k}{dist(v_i, v_j) \times X_{v_j}} \right\}}$를 구해 출력한다. $dist(v_i, v_j)$는 $v_i$에서 $v_j$로 가는 경로에 있는 모든 간선의 가중치를 더한 값이다.

입력

첫째 줄에 정점의 개수 $N$, 쿼리의 개수 $Q$가 주어진다. 둘째 줄부터 Q개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

입력으로 주어지는 쿼리의 정점 번호(1, 2번 쿼리의 $a$, $b$, 3번 쿼리의 $a$)는 암호화 되어 있어 쿼리를 수행하기 전에 해독해야 한다. 입력으로 주어진 정점 번호가 $x$이고, 이전 3번 쿼리에서 구한 값이 $S$인 경우 해독한 정점의 번호는 $(x-1+S) \bmod {n} + 1$ 이다.

출력

3번 쿼리에서 구한 값을 한 줄에 하나씩 쿼리가 주어진 순서대로 출력한다.

제한

  • $1 \le N \le 10^5$
  • $1 \le Q \le 3 \times 10^5$
  • $1 \le a, b \le N$
  • $a \ne b$
  • $1 \le c \le 10^8$

예제 입력 1

3 7
1 1 2 3
1 3 1 1
3 1
2 1 3
3 1
1 2 1 2
3 2

예제 출력 1

4
0
0

첫 번째 3번 쿼리가 주어진 경우, 정점 $1$과 $2$ 사이에 가중치가 $3$인 간선이 있고, 정점 $1$과 $3$ 사이에 가중치가 $1$인 간선이 있는 상황이다. 쿼리로 인해 $X_1$은 $1$에서 $0$으로 변하고, $X_1 = 0, X_2 = 1, X_3 = 1$이다. 쿼리의 결과는 $dist(1, 1) \times X_1 + dist(1, 2) \times X_2 + dist(1, 3) \times X_3 = 4$이다.

다음 2번 쿼리의 정점 번호 $1$, $3$은 $(1 - 1 + 4) \bmod {3} + 1 = 2$, $(3 - 1 + 4) \bmod{3} + 1 = 1$로 해독할 수 있다.

두 번째 3번 쿼리로 인해 $X_2$의 값이 $1$에서 $0$으로 변한다. 정점 $2$가 포함된 트리에는 정점 $2$만 있기 때문에, 쿼리의 결과는 $0$이다.

세 번째 3번 쿼리가 주어진 경우, 정점 $1$과 $3$ 사이에 가중치가 $1$인 간선이 있고, 정점 $2$와 $3$ 사이에 가중치가 $2$인 간선이 있는 상황이다. 쿼리로 인해 $X_3$은 $1$에서 $0$으로 변하고, $X_1 = 0, X_2 = 0, X_3 = 0$이다. 쿼리의 결과는 $0$이다.

예제 입력 2

5 17
1 1 5 10
1 3 1 7
1 5 2 5
1 3 4 2
2 3 1
1 4 1 6
2 5 2
3 1
3 2
3 2
1 2 1 2
3 4
2 5 1
1 4 5 2
2 3 4
1 3 5 9
3 5

예제 출력 2

18
2
0
0
9

예제 입력 3

10 37
1 2 3 6428496
1 7 10 41603701
1 2 7 61903527
1 1 6 57606292
1 2 1 43682226
1 8 2 59090781
3 6
3 10
1 10 7 15269842
3 6
3 7
1 3 10 39799671
1 3 5 28501778
3 5
2 1 10
1 6 10 37641690
2 9 6
3 8
1 6 8 89420938
3 9
2 6 3
1 9 6 17757145
2 9 3
1 1 9 26575112
2 3 8
1 2 1 19670627
2 3 5
1 1 5 12760556
2 3 4
1 4 1 36949637
3 7
2 6 9
1 6 8 74850387
2 3 8
3 3
1 7 3 77007154
3 3

예제 출력 3

274612258
215521477
187109093
171839251
211638922
68332023
151324465
224010174
0
223740409