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 ≤ 10⁵) — the number of workers Pavel hired.

Each of the following n lines contains three space-separated integers l _i, v _i, r _i (1 ≤ l _i ≤ v _i ≤ r _i ≤ 3·10⁵) — 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

4
2 8 9
1 4 7
3 6 8
5 8 10

output

3
1 3 4

input

6
3 5 16
1 6 11
4 8 12
7 9 16
2 10 14
8 13 15

output

4
1 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;

int max[TREE], add[TREE], index[TREE];

void build(int x, int l, int r) {
max[x] = add[x] = 0;
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) {
    add[x] += v;
    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;
}