import java.io.*;
import java.util.*;

class Solution {
  public static int kthSmallest(int[] a, int[] b, int k) {
    k = Math.min(k, a.length + b.length);

    int ai = 0, bi = 0;
    int r = 0;
    for (int i = 0; i < k; i++)
      if (ai >= a.length || bi < b.length && a[ai] >= b[bi]) r = b[bi++];
      else r = a[ai++];

    return r;
  }

  public static void main(String[] args) {
    Random random = new Random();

    int szA = 4;
    int szB = 5;

    int[] a = new int[szA];
    a[0] = random.nextInt(10);
    for (int i = 1; i < a.length; i++)
      a[i] = a[i-1] + (random.nextInt(1) == 0 ? random.nextInt(10): 0 );

    int[] b = new int[szB];
    b[0] = random.nextInt(10);
    for (int i = 1; i < b.length; i++)
      b[i] = b[i-1] + (random.nextInt(1) == 0 ? random.nextInt(10): 0 );

    boolean allGood = true;

    for (int t = 1; t <= 12; t++) {
      for (int k = 1; k <= a.length + b.length; k++) {
        int actual = kthSmallest(a,b,k);

        ArrayList<Integer> merged = new ArrayList<>();
        for (int x: a) merged.add(x);
        for (int x: b) merged.add(x);
        Collections.sort(merged);

        int expected = merged.get(k-1);

        if (actual != expected) {
          System.out.print("FAILED k=" + k + " a=" + Arrays.toString(a) + " b=" + Arrays.toString(b)
                             + " expected=" + expected + " actual=" + actual + " merged=[");
          for (int x: merged) System.out.print(x + ", ");
          System.out.println("]");

          allGood = false;
        }
      }
    }

    System.out.println(allGood ? "ALL OK": "FAILED");
  }
}