import java.util.*;

public class Solution {
    public static List<Integer> mergeThreeSortedArrays(int[] A, int[] B, int[] C) {
        List<Integer> result = new ArrayList<>();
        int i = 0, j = 0, k = 0;
        int n1 = A.length, n2 = B.length, n3 = C.length;

        while (i < n1 || j < n2 || k < n3) {
            int minVal = Integer.MAX_VALUE;
            if (i < n1) minVal = Math.min(minVal, A[i]);
            if (j < n2) minVal = Math.min(minVal, B[j]);
            if (k < n3) minVal = Math.min(minVal, C[k]);

            if (i < n1 && A[i] == minVal) i++;
            else if (j < n2 && B[j] == minVal) j++;
            else k++; // C[k] must be the smallest
            
            result.add(minVal);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] A = {1, 4, 7};
        int[] B = {2, 5, 8};
        int[] C = {3, 6, 9};
        System.out.println(mergeThreeSortedArrays(A, B, C)); 
        // Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}