안전한 철판 2

어떤 광선이 있다. 이 광선에 철판이 닿으면 철판이 녹는다.

광선의 세기를 올리면 앞선 철판을 녹이고 광선의 세기는 약해지며 그 다음에 부딪치는 철판까지도 녹일 수 있다.

아래 그림을 보자. 아래 그림은 위에서 본 그림이고 철판은 모두 세워져 있는 형태이다.

만일 광선의 세기가 1, 즉 하나의 철판을 녹일수 있는 정도라면 위의 그림에서와 같이 광선이 왼쪽에서 오른쪽으로 평행하게 나간다면, 광선과 조금도 접촉하지 않고 안전한 철판은 "2, 4"이다. "6"은 윗부분에서 닿아 철판이 녹는다.

만일 광선의 세기가 2라면, 즉 2개의 철판을 녹일 수 있다면 철판 "1"을 녹인 광선이 약해지고 2번 철판을 녹인다.

또 "1, 5, 2"번 철판에 닿지 않고 지나온 광선이 3번을 녹이면서 4번도 녹이므로 광선의 세기가 2에서는 안전한 철판이 아무것도 없다.

광선의 세기와 철판이 주어졌을 때 안전한 철판을 찾아라. 단, 각 철판은 그림과 같이 모두 수직방향으로 서 있다.

입력

입력의 처음에는 100,000 이하의 자연수인 광선의 세기가 주어진다.

그 다음 줄에 철판의 개수가 주어진다.

철판의 개수는 100,000개 이하이다. 그 다음 줄부터 한 줄에 각 철판의 정보 n, x_n, y_min, y_max가 주어진다.

n은 철판의 번호이며 양의 정수이다. x_n은 철판의 놓여진 x축의 좌표이다.

y_min, y_max는 y축의 최저값과 최대값이다. (y_min< y_max)

x축과 y축의 좌표는 100,000,000 이하의 자연수이다.

철판이 겹친 상태는 주어지지 않는다. (어느 철판의 시작점과 다른 철판의 끝점이 일치할 경우, 겹친 상태가 아니다.)

출력

안전한 철판의 번호를 오름차순으로 정렬하여 한 줄에 공백으로 구분하여 모두 출력한다.

단, 안전한 철판이 하나도 없다면 0을 출력한다.

예제1

예제2

예제3

힌트

출처

@eva

안전한 철판 2 1초 128MB