import java.util.*;

class Solution {

  public List<List<Integer>> searchQuadruplets(int[] arr, int target) {
    List<List<Integer>> quadruplets = new ArrayList<>();
    Arrays.sort(arr);
    for(int i = 0; i < arr.length - 3; i++){
        while(i > 0 && arr[i-1] == arr[i]){
          continue;
        }
        findAndPushTriplet(arr, i, quadruplets, target);
    }
    return quadruplets;
  }

  public static void findAndPushTriplet(int[] arr, int firstIndex, List<List<Integer>> quadruplets, int requiredTarget){
    boolean first = true;
    int j = firstIndex + 1;
    while(j < arr.length - 2){
        
        while(!first && arr[j] == arr[j-1] && j < arr.length - 2 ){
          j++;
        } 

        int left = j+1;
        int right = arr.length - 1;
        first = false;
        while(left < right){
          int sum = arr[left] + arr[right] + arr[j] + arr[firstIndex];
          if(sum == requiredTarget){
            List<Integer> quadruplet = new ArrayList<>();
            quadruplet.add(arr[firstIndex]);
            quadruplet.add(arr[j]);
            quadruplet.add(arr[left]);
            quadruplet.add(arr[right]);
            quadruplets.add(quadruplet);
            left++;
            right--;
            while(left < right && arr[left] == arr[left - 1]){
              left++;
            }
            while(left < right && arr[right] == arr[right - 1]){
              right-- ;
            }
          } else if(sum < requiredTarget){
            left ++;
          } else if (sum > requiredTarget){
            right--;
          }
        }
        j++;
    }
  }
}