만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

송유관 II

시간 제한4초메모리 제한1024 MB

요약
각 발전소는 구간 [L, R] 안의 지점에 공급되는 연료 합계가 T 이상이어야 가동된다. 2번 이벤트마다 새로 가동되는 발전소 번호를 오름차순으로 출력합니다.
난이도

어려움10점 중 8점

유형
세그먼트 트리, 구현, 구간
정답자
아직 제출이 없습니다

문제

새로 설립된 산업 단지에 발전소가 계속해서 들어서고 있다. 산업 단지에는 NN개의 주유소가 11번부터 NN번까지 일렬로 놓여 있고, 발전소는 주유소를 통해 기름을 공급받고자 한다.

이때 다음과 같은 이벤트가 주어진다.

  • 11 LL RR TT: 새로운 발전소가 산업 단지에 들어왔다. 이 발전소는 TT 이상의 기름을 공급받아야 가동된다. LL번 주유소부터 RR번 주유소까지 R−L+1R-L+1개의 주유소에 송유관을 일렬로 설치한다. 이 발전소 전에 산업 단지에 들어온 발전소의 개수가 PP개라면 이 발전소의 번호는 P+1P+1이다.
  • 22 II CC: II번 주유소에 송유관이 설치된 모든 발전소에 각각 CC만큼의 기름을 공급한다. 이 이벤트 직후에 가동된 발전소가 있다면 가동된 발전소의 개수와 발전소의 번호들을 출력한다. 이 이벤트 전에 가동된 발전소는 출력에 포함하지 않는다.

입력

첫 번째 줄에 주유소의 수 NN과 이벤트의 개수 QQ가 정수로 주어진다. (1≤N≤100 0001 \le N \le 100\,000, 1≤Q≤500 0001 \le Q \le 500\,000)

다음 QQ개의 줄에는 이벤트에 대한 정보가 주어진다. 두 번째 유형의 마지막 이벤트에서 조건을 만족한 발전소의 개수를 lastlast라고 한다. 1번 이벤트는 11 xx yy TT 형태로 주어지며, L=x⊕lastL = x \oplus last, R=y⊕lastR = y \oplus last로 정의된다. 2번 이벤트는 22 zz CC 형태로 주어지며, I=z⊕lastI = z \oplus last로 정의된다. (1≤L≤R≤N1 \le L \le R \le N, 1≤I≤N1 \le I \le N, 1≤T≤500 0001 \le T \le 500\,000, 1≤C≤500 0001 \le C \le 500\,000)

입력에서 생성된 LL, RR, II 값이 범위를 벗어나지 않음이 보장된다. 두 번째 유형의 첫 번째 이벤트가 처리되기 전까지 lastlast의 값은 0이다.

출력

두 번째 유형의 각 이벤트에 대해 정답을 한 줄씩 출력한다. 각 줄에는 이 이벤트에서 새로 가동된 발전소의 개수를 정수로 쓰고, 이어서 가동된 발전소의 번호를 오름차순으로 쓴다.

예제1

  1. 예제 1

    입력
    13 7
    1 1 3 5
    2 2 3
    1 1 12 6
    2 11 5
    2 1 4
    1 3 6 5
    2 3 5
    
    예상 출력
    0
    0
    2 1 2
    1 3