만드는 중입니다

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

송유관 I

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

요약
2번 이벤트마다 역 I를 지나는 배관을 가진 발전소에 C를 더하고, 새로 가동되는 발전소의 번호를 오름차순으로 출력합니다.
난이도

보통10점 중 6점

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

문제

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

다음 두 종류의 이벤트가 주어진다.

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

입력

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

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

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

출력

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

예제1

  1. 예제 1

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