description: On an endless checkered sheet of paper, n cells are chosen and colored in three colors, where n is divisible by 3. It turns out that there are exactly n/3 marked cells of each of three colors! 
  
  Find the largest such k that it's possible to choose k/3 cells of each color, remove all other marked cells, and then select three rectangles with sides parallel to the grid lines so that the following conditions hold:
  
    * No two rectangles can intersect (but they can share a part of the boundary). In other words, the area of intersection of any two of these rectangles must be 0.
    * The i-th rectangle contains all the chosen cells of the i-th color and no chosen cells of other colors, for i = 1, 2, 3. 
  
  Input
  
  The first line of the input contains a single integer n — the number of the marked cells (3 ≤ n ≤ 10^5, n is divisible by 3).
  
  The i-th of the following n lines contains three integers x_i, y_i, c_i (|x_i|,|y_i| ≤ 10^9; 1 ≤ c_i ≤ 3), where (x_i, y_i) are the coordinates of the i-th marked cell and c_i is its color.
  
  It's guaranteed that all cells (x_i, y_i) in the input are distinct, and that there are exactly n/3 cells of each color.
  
  Output
  
  Output a single integer k — the largest number of cells you can leave.
  
  Examples
  
  Input
  
  
  9
  2 3 1
  4 1 2
  2 1 3
  3 4 1
  5 3 2
  4 4 3
  2 4 1
  5 2 2
  3 5 3
  
  
  Output
  
  
  6
  
  
  Input
  
  
  3
  1 1 1
  2 2 2
  3 3 3
  
  
  Output
  
  
  3
  
  Note
  
  In the first sample, it's possible to leave 6 cells with indexes 1, 5, 6, 7, 8, 9.
  
  In the second sample, it's possible to leave 3 cells with indexes 1, 2, 3.
solution: import java.io.OutputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.io.PrintWriter;
  import java.util.Arrays;
  import java.util.StringTokenizer;
  import java.io.IOException;
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.io.InputStream;
  
  /**
   * Built using CHelper plug-in
   * Actual solution is at the top
   */
  public class Main {
      public static void main(String[] args) {
          InputStream inputStream = System.in;
          OutputStream outputStream = System.out;
          FastScanner in = new FastScanner(inputStream);
          PrintWriter out = new PrintWriter(outputStream);
          TaskE solver = new TaskE();
          solver.solve(1, in, out);
          out.close();
      }
  
      static class TaskE {
          public void solve(int testNumber, FastScanner in, PrintWriter out) {
              int n = in.nextInt();
              int[] x = new int[n];
              int[] y = new int[n];
              int[] col = new int[n];
              for (int i = 0; i < n; i++) {
                  x[i] = in.nextInt();
                  y[i] = in.nextInt();
                  col[i] = in.nextInt() - 1;
              }
              Point[] p = new Point[n];
              for (int i = 0; i < n; i++) {
                  p[i] = new Point(x[i], y[i], col[i], i);
              }
  
              int[] byX = new int[n];
              Arrays.sort(p, (u, v) -> (Integer.compare(u.x, v.x)));
              for (int i = 0; i < n; i++) {
                  byX[i] = p[i].id;
              }
              int[] byY = new int[n];
              Arrays.sort(p, (u, v) -> (Integer.compare(u.y, v.y)));
              for (int i = 0; i < n; i++) {
                  byY[i] = p[i].id;
              }
              Arrays.sort(p, (u, v) -> (Integer.compare(u.id, v.id)));
  
              int[][] perm3 = {
                      {0, 1, 2},
                      {0, 2, 1},
                      {1, 0, 2},
                      {1, 2, 0},
                      {2, 0, 1},
                      {2, 1, 0},
              };
  
              int l = 0;
              int r = n / 3 + 1;
              int[] nByX = new int[n];
              int[] nByY = new int[n];
              while (r - l > 1) {
                  int m = (l + r) / 2;
                  boolean ok = false;
                  outer:
                  for (int[] perm : perm3) {
                      for (int rot = 0; rot < 4; rot++) {
                          if (can(p, byX, byY, perm, m)) {
                              ok = true;
                              break outer;
                          }
  
                          for (int i = 0; i < n; i++) {
                              nByX[i] = byY[n - 1 - i];
                              nByY[i] = byX[i];
                              p[i].rotate90();
                          }
  
                          int[] t = byX;
                          byX = nByX;
                          nByX = t;
  
                          t = byY;
                          byY = nByY;
                          nByY = t;
                      }
                  }
                  if (ok) {
                      l = m;
                  } else {
                      r = m;
                  }
              }
              out.println(3 * l);
          }
  
          private boolean can(Point[] p, int[] byX, int[] byY, int[] perm, int k) {
              return can0(p, byX, byY, perm, k) || can1(p, byX, byY, perm, k);
          }
  
          private boolean can0(Point[] p, int[] byX, int[] byY, int[] perm, int k) {
              // One to the left, one to the right, one in-between.
              int borderX = Integer.MIN_VALUE;
              int cur = 0;
              for (int i : byX) {
                  if (p[i].col == perm[0]) {
                      ++cur;
                      if (cur == k) {
                          borderX = p[i].x;
                          break;
                      }
                  }
              }
  
              int newBorderX = Integer.MIN_VALUE;
              cur = 0;
              for (int i : byX) {
                  if (p[i].col == perm[1] && p[i].x > borderX) {
                      ++cur;
                      if (cur == k) {
                          newBorderX = p[i].x;
                          break;
                      }
                  }
              }
              if (cur < k) {
                  return false;
              }
  
              cur = 0;
              for (int i = 0; i < p.length; i++) {
                  if (p[i].col == perm[2] && p[i].x > newBorderX) {
                      ++cur;
                      if (cur == k) {
                          return true;
                      }
                  }
              }
  
              return false;
          }
  
          private boolean can1(Point[] p, int[] byX, int[] byY, int[] perm, int k) {
              // One to the left, two to the right on top one another.
              int borderX = Integer.MIN_VALUE;
              int cur = 0;
              for (int i : byX) {
                  if (p[i].col == perm[0]) {
                      ++cur;
                      if (cur == k) {
                          borderX = p[i].x;
                          break;
                      }
                  }
              }
  
              int borderY = Integer.MIN_VALUE;
              cur = 0;
              for (int i : byY) {
                  if (p[i].col == perm[1] && p[i].x > borderX) {
                      ++cur;
                      if (cur == k) {
                          borderY = p[i].y;
                          break;
                      }
                  }
              }
              if (cur < k) {
                  return false;
              }
  
              cur = 0;
              for (int i = 0; i < p.length; i++) {
                  if (p[i].col == perm[2] && p[i].x > borderX && p[i].y > borderY) {
                      ++cur;
                      if (cur == k) {
                          return true;
                      }
                  }
              }
  
              return false;
          }
  
          class Point {
              int x;
              int y;
              int col;
              int id;
  
              public Point(int x, int y, int col, int id) {
                  this.x = x;
                  this.y = y;
                  this.col = col;
                  this.id = id;
              }
  
              public void rotate90() {
                  int nx = -y;
                  int ny = x;
                  x = nx;
                  y = ny;
              }
  
          }
  
      }
  
      static class FastScanner {
          private BufferedReader in;
          private StringTokenizer st;
  
          public FastScanner(InputStream stream) {
              try {
                  in = new BufferedReader(new InputStreamReader(stream, "UTF-8"));
              } catch (Exception e) {
                  throw new AssertionError();
              }
          }
  
          public String next() {
              while (st == null || !st.hasMoreTokens()) {
                  try {
                      String rl = in.readLine();
                      if (rl == null) {
                          return null;
                      }
                      st = new StringTokenizer(rl);
                  } catch (IOException e) {
                      throw new RuntimeException(e);
                  }
              }
              return st.nextToken();
          }
  
          public int nextInt() {
              return Integer.parseInt(next());
          }
  
      }
  }
  
  