시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 18 10 7 58.333%

문제

대문 밖을 나서고 입대가 초읽기로 다가오자, 초조해지는 마음에 욱제는 가슴을 마구 내리쳤다. 그러자 평소 심혈관계 건강이 좋지 않았던 욱제의 모세 혈관들이 모두 파열되어 버렸다.

젊은 욱제의 심혈관계는 1번부터 N번까지 번호가 붙은 N개의 세포와 서로 다른 두 세포 사이를 연결하여 혈액을 공급하는 혈관으로 표현할 수 있다. 몇 개의 혈관들을 통해 연결된 두 세포 사이에는 혈액이 흐를 수 있다. 욱제가 가슴을 마구 내리쳤기 때문에 처음에는 어떤 혈관도 남아있지 않다. 시간이 흐름에 따라 젊은 욱제의 혈관은 생성되고 터지기를 반복한다. 혈관 x의 강도는 한계 심박수 Dx로 표현되는데, 긴장한 욱제의 심박수가 Dx를 초과하면 이 혈관은 견디지 못하고 터져버린다. 

계속 혈관이 생기고 터지면서 멍이 들자, 욱제는 세포들 사이에 혈액이 원활하게 공급되고 있는지 걱정되어 자가 진단 기계를 만들고자 한다. 즉, 욱제는 위에 주어진 3가지 쿼리를 처리하는 기계를 만들고자 한다.

  • 1 i j d : i번 세포와 j번 세포를 직접 잇는 한계 심박수 d인 혈관이 생성된다. (i ≠ j) 두 세포 사이에 여러 개의 온전한 혈관이 동시에 존재하는 일은 없다.
  • 2 x : 욱제의 심박수가 순간적으로 x로 변화한다. 이 사건이 일어나는 시점 이외에 욱제의 심박수는 충분히 낮아 0으로 가정해도 좋다.
  • 3 i j : 이 쿼리가 주어진 시점에 i번 세포와 j번 세포 사이에 혈액이 흐를 수 있는 욱제의 최대 심박수 x를 출력한다. (i ≠ j)

하지만 욱제는 계속 가슴을 내리치느라 손에 멍이 들어 코딩을 할 수가 없다. 여러분이 이 질문을 대신 처리해주도록 하자.

입력

첫째 줄에 세포의 개수 N과 쿼리의 개수 Q가 주어진다.

둘째 줄부터 Q개의 줄에 걸쳐 쿼리들이 입력으로 주어진다. 

출력

3번 쿼리가 주어질 때마다 그에 대한 답을 출력한다. 해당 시점에 두 세포 사이에 혈액이 흐를 수 없다면 0을 출력한다.

제한

  • 2 ≤ N ≤ 316,000
  • 1 ≤ Q ≤ 402,000
  • 1번 쿼리에서 1 ≤ d ≤ 109
  • 2번 쿼리에서 1 ≤ x ≤ 109
  • 3번 쿼리가 하나 이상 존재한다.
  • 입력의 모든 값은 음 아닌 정수이다.

예제 입력 1

3 6
1 1 2 100
1 2 3 200
1 1 3 300
3 1 2
3 1 3
3 2 3

예제 출력 1

200
300
200

예제 입력 2

6 9
1 1 2 3
1 2 3 4
1 4 5 5
1 5 6 6
3 1 3
3 1 5
2 4
3 1 3
3 2 3

예제 출력 2

3
0
0
4

예제 입력 3

3 9
1 1 2 9
1 2 3 6
3 1 3
3 1 2
2 7
3 1 3
1 2 3 10
2 9
3 2 3

예제 출력 3

6
9
0
10

예제 입력 4

11 21
1 10 11 57
3 10 11
1 3 11 78
2 100
1 5 11 36
1 10 11 31
3 8 9
1 7 9 29
1 7 10 133
1 7 8 60
3 3 10
1 2 5 90
1 9 11 141
1 8 9 123
3 8 11
3 2 5
2 17
3 2 5
1 6 11 57
1 4 10 127
3 7 11

예제 출력 4

57
0
0
123
90
90
60