문제

진흥이에게는 시작점과 끝점이 정해진 구간이 여러 개 주어집니다. 각 구간은 서로 겹칠 수도 있고, 겹치지 않을 수도 있습니다.

진흥이는 구간들이 서로 전혀 겹치지 않도록 만들고 싶어 합니다. 이를 위해 몇 개의 구간을 지워야 할 수도 있습니다. 구간 와 가 있을 때, 이거나 이면 두 구간이 서로 겹친다고 합니다.

처음에 개의 구간이 주어지면, 여러분은 진흥이를 도와 다음과 같은 질의를 개 처리해야 합니다.

• : 구간 를 하나 추가합니다.
• : 이미 존재하는 구간 를 하나 삭제합니다.
• : 모든 구간 가 를 만족하면서 서로 겹치지 않도록 할 때, 삭제해야 하는 구간의 최소 개수를 출력하세요. 실제로 삭제하지는 않습니다.

진흥이와 함께 질의를 처리해 봅시다.

입력

첫 번째 줄에 초기 구간의 개수 과 질의의 개수 가 주어집니다.

다음 개의 줄에 걸쳐 각 구간의 시작점 와 끝점 가 공백으로 구분되어 주어집니다.

이후 개의 줄에 걸쳐 각 질의를 나타내는 정수 , , 가 공백으로 구분되어 주어집니다.

출력

인 질의마다 조건을 만족하도록 만들기 위해 삭제해야 하는 구간의 최소 개수를 한 줄에 하나씩 출력합니다.

노트

• 가 일 때, 구간 가 존재합니다.
• 가 인 질의가 하나 이상 존재합니다.