# Developing Game

Pavel is going to make a game of his dream. However, he knows that he can’t make it on his own so he founded a development company and hired n workers of staff. Now he wants to pick n workers from the staff who will be directly responsible for developing a game.

Each worker has a certain skill level v i. Besides, each worker doesn’t want to work with the one whose skill is very different. In other words, the i-th worker won’t work with those whose skill is less than l i, and with those whose skill is more than r i.

Pavel understands that the game of his dream isn’t too hard to develop, so the worker with any skill will be equally useful. That’s why he wants to pick a team of the maximum possible size. Help him pick such team.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of workers Pavel hired.

Each of the following n lines contains three space-separated integers l iv ir i (1 ≤ l i ≤ v i ≤ r i ≤ 3·105) — the minimum skill value of the workers that the i-th worker can work with, the i-th worker’s skill and the maximum skill value of the workers that the i-th worker can work with.

Output

In the first line print a single integer m — the number of workers Pavel must pick for developing the game.

In the next line print m space-separated integers — the numbers of the workers in any order.

If there are multiple optimal solutions, print any of them.

Examples

input

42 8 91 4 73 6 85 8 10

output

31 3 4

input

63 5 161 6 114 8 127 9 162 10 148 13 15

output

41 2 3 5

Solution:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>

const int co = 300000;
const int TREE = 10 * co + 10;

void build(int x, int l, int r) {
index[x] = l;
if (l < r) {
int y = (l + r) >> 1;
build(x + x, l, y);
build(x + x + 1, y + 1, r);
}
}

void modify(int x, int l, int r, int ll, int rr, int v) {
if (r < ll || rr < l) return;
if (l >= ll && r <= rr) {
return;
}
int y = (l + r) >> 1;
modify(x + x, l, y, ll, rr, v);
modify(x + x + 1, y + 1, r, ll, rr, v);
int wl = max[x + x] + add[x + x];
int wr = max[x + x + 1] + add[x + x + 1];
if (wl > wr) {
max[x] = wl;
index[x] = index[x + x];
} else {
max[x] = wr;
index[x] = index[x + x + 1];
}
}

const int N = 100010;

int low[N], v[N], high[N];
int r[N];

std::vector <int> left[co + 10], skill[co + 10];

int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d %d %d", low + i, v + i, high + i);
for (int i = 1; i <= co; i++) {
left[i].clear();
skill[i].clear();
}
for (int i = 1; i <= n; i++) {
left[low[i]].push_back(i);
skill[v[i]].push_back(i);
}
build(1, 1, co);
int ans = 0, a_from = 0, a_to = 0;
for (int from = 1; from <= co; from++) {
{
int sz = left[from].size();
for (int j = 0; j < sz; j++) {
int id = left[from][j];
modify(1, 1, co, v[id], high[id], 1);
}
}
int cur = max[1] + add[1];
if (cur > ans) {
ans = cur;
a_from = from;
a_to = index[1];
}
{
int sz = skill[from].size();
for (int j = 0; j < sz; j++) {
int id = skill[from][j];
modify(1, 1, co, v[id], high[id], -1);
}
}
}
int kr = 0;
for (int i = 1; i <= n; i++)
if (low[i] <= a_from && a_from <= v[i] && v[i] <= a_to && a_to <= high[i]) {
r[++kr] = i;
}
printf("%d\n", kr);
for (int i = 1; i < kr; i++) printf("%d ", r[i]);
printf("%d\n", r[kr]);
return 0;
}