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.*;
  import java.util.*;
   
  public class Solution extends PrintWriter {
      
      int[][] perm = new int[][] {{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
      
      void solve() {
          n = sc.nextInt();
          cells = new int[n][];
          for(int i = 0; i < n; i++) {
              cells[i] = new int[] {sc.nextInt(), sc.nextInt(), sc.nextInt()-1, 0};
          }
          
          int ans = 0;
          for(int it = 0; it < 2; it++) {
              sort();
              pre_pos_by_y();
  
              int l = 0;
              int r = n/3+1;
              while(l < r-1) {
                  int mid = (l+r)/2;
                  if(pre_case1(mid)) l = mid;
                  else r = mid;
              }
              ans = Math.max(ans, l);
              l = 0;
              r = n/3+1;
              while(l < r-1) {
                  int mid = (l+r)/2;
                  if(pre_case2(mid, false)) l = mid;
                  else r = mid;
              }
              reverse();
              pre_pos_by_y();
              ans = Math.max(ans, l);
              l = 0;
              r = n/3+1;
              while(l < r-1) {
                  int mid = (l+r)/2;
                  if(pre_case2(mid, true)) l = mid;
                  else r = mid;
              }
              ans = Math.max(ans, l);
              invert_axis();
          }
          println(3*ans);
      }
      
      int[] pos_by_y;
      
      void sort() {
          Arrays.sort(cells, Comparator.comparing(arr -> arr[1]));
          for(int i = 0; i < n; i++) {
              cells[i][3] = i;
          }
          
          Arrays.sort(cells, Comparator.comparing(arr -> arr[0]));
          
      }
      
      void pre_pos_by_y() {
          pos_by_y = new int[n];
          for(int i = 0; i < n; i++) {
              pos_by_y[cells[i][3]] = i;
          }
      }
      
      int n;
      int[][] cells;
      
      boolean pre_case1(int k) {
          for(int[] p : perm) {
              if(case1(p, k)) return true;
          }
          return false;
      }
      
      boolean case1(int[] type, int k) {
          int cnt = 0;
          int idx = 0;
          int last_x = -1<<30;
          for(int it = 0; it <= 2; it++) {
              cnt = 0;
              for(; idx < n && cnt < k; idx++) {
                  if(cells[idx][0] > last_x && cells[idx][2] == type[it]) {
                      cnt++;
                  }                
              }
              if(cnt < k) return false;
              last_x = cells[idx-1][0];
          }
          return true;
      }
      
      boolean pre_case2(int k, boolean reversed) {
          for(int[] p : perm) {
              if(case2(p, k, reversed)) return true;
          }
          return false;
      }
      
      boolean case2(int[] type, int k, boolean reversed) {
          int cnt = 0;
          int idx = 0;
          cnt = 0;
          for(; idx < n && cnt < k; idx++) {
              if(cells[idx][2] == type[0]) {
                  cnt++;
              }                
          }
          if(cnt < k) return false;
          int last_x = cells[idx-1][0];
          idx = 0;
          int last_y = -1<<30;
          for(int it = 1; it <= 2; it++) {
              cnt = 0;
              for(; idx < n && cnt < k; idx++) {
                  if(cells[pos_by_y[idx]][2] == type[it] && after(cells[pos_by_y[idx]][0], last_x, reversed) && cells[pos_by_y[idx]][1] > last_y) {
                      cnt++;
                  }  
              }
              if(cnt < k) return false;
              last_y = cells[pos_by_y[idx-1]][1];
          }
          return true;
      }
      
      boolean after(int x1, int x2, boolean reversed) { //x1 > x2
          if(reversed) return x1 < x2;
          else return x1 > x2;
      }
      
      void reverse() {
          for(int i = 0; i < n/2; i++) {
              int[] temp = cells[i];
              cells[i] = cells[n-1-i];
              cells[n-1-i] = temp;
          }
      }
      
      void invert_axis() {
          for(int i = 0; i < n; i++) {
              int temp = cells[i][0];
              cells[i][0] = cells[i][1];
              cells[i][1] = temp;
          }
      }
      
          
  //  Main() throws FileNotFoundException { super(new File("output.txt")); }
  //  InputReader sc = new InputReader(new FileInputStream("test_input.txt"));
    Solution() { super(System.out); }
    InputReader sc = new InputReader(System.in);
    static class InputReader {
        InputReader(InputStream in) { this.in = in; } InputStream in;
        
        private byte[] buf = new byte[16384];
        private int    curChar;
        private int    numChars;
        
   
        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
   /*
        private String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }*/
   
        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
   
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
   
        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
   
        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
   
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
   
      public static void main(String[] $) {
          new Thread(null, new Runnable() {
              public void run() {
                  long start = System.nanoTime();
                  try {Solution solution = new Solution(); solution.solve(); solution.flush();} 
                  catch (Exception e) {e.printStackTrace(); System.exit(1);}
                  System.err.println((System.nanoTime()-start)/1E9);
              }
          }, "1", 1 << 27).start();
   
      }
  }