import java.util.*;

/** Tested teaching solutions for the recursion problem articles. Java 17+. */
public class RecursionProblemExamples {
    public static List<List<Integer>> permuteBrute(int n) {
        List<List<Integer>> answer = new ArrayList<>(); // Retain only valid complete permutations.
        buildAllPermutations(n, new ArrayList<>(), new boolean[n + 1], answer); // Initially all values are free.
        return answer; // Ascending candidate choices already order the accepted outputs.
    }

    private static void buildAllPermutations(int n, List<Integer> path,
                                             boolean[] used, List<List<Integer>> answer) {
        if (path.size() == n) { // Brute force delays parity checks until every position is filled.
            for (int i = 1; i < n; i++) { // The first adjacent pair ends at index one.
                if (path.get(i - 1) % 2 == path.get(i) % 2) return; // Reject the whole permutation.
            }
            answer.add(new ArrayList<>(path)); // Later backtracking must not mutate this saved result.
            return; // There are no remaining positions to fill.
        }
        for (int candidate = 1; candidate <= n; candidate++) { // Try the smallest next value first.
            if (used[candidate]) continue; // Each integer may appear only once in a permutation.
            used[candidate] = true; // Reserve this value for the current branch.
            path.add(candidate); // Record its position, even if the prefix has invalid parity.
            buildAllPermutations(n, path, used, answer); // Generate every completion before filtering.
            path.remove(path.size() - 1); // Restore the parent prefix after the child returns.
            used[candidate] = false; // The next sibling must be allowed to choose this value again.
        }
    }

    public static List<List<Integer>> permute(int n) {
        List<List<Integer>> answer = new ArrayList<>(); // Each saved list will be a separate object.
        boolean[] used = new boolean[n + 1]; // Index zero is unused because the values are 1 through n.
        buildAlternating(n, new ArrayList<>(), used, answer); // Begin with no chosen numbers.
        return answer; // DFS with ascending candidates gives lexicographic order without sorting.
    }

    private static void buildAlternating(int n, List<Integer> path,
                                         boolean[] used, List<List<Integer>> answer) {
        if (path.size() == n) { // A valid prefix has now used every required number.
            answer.add(new ArrayList<>(path)); // Copy: the shared path will shrink on return.
            return; // Stop this branch; a permutation cannot contain more than n values.
        }
        for (int candidate = 1; candidate <= n; candidate++) { // Smaller next values come first.
            if (used[candidate]) continue; // Do not repeat a number already in this branch.
            if (!path.isEmpty() && path.get(path.size() - 1) % 2 == candidate % 2) {
                continue; // Equal remainders mean odd/odd or even/even: reject before recursing.
            }
            if (path.isEmpty() && n % 2 == 1 && candidate % 2 == 0) {
                continue; // Odd n has one extra odd number, so only odd-start patterns can finish.
            }
            used[candidate] = true; // Make this number unavailable while the child explores.
            path.add(candidate); // Extend the valid prefix by exactly one value.
            buildAlternating(n, path, used, answer); // Ask the child to fill the remaining positions.
            path.remove(path.size() - 1); // The child has returned; undo our own appended value.
            used[candidate] = false; // Restore availability for the next candidate and parent.
        }
    }

    public static void reverseStack(Deque<Integer> stack) {
        if (stack.isEmpty()) return; // An empty stack is already reversed; stop descending.
        int top = stack.pop(); // Save this value in this call frame, not in another collection.
        reverseStack(stack); // Trust the smaller stack to reverse before this call resumes.
        insertBottom(stack, top); // The old top belongs below every reversed remaining value.
    }

    private static void insertBottom(Deque<Integer> stack, int value) {
        if (stack.isEmpty()) { // We reached the bottom: there is nothing below value.
            stack.push(value); // Place the saved old top at the bottom.
            return; // Do not pop the value we just inserted.
        }
        int top = stack.pop(); // Temporarily expose the next deeper position.
        insertBottom(stack, value); // Keep descending until the bottom is exposed.
        stack.push(top); // Restore this displaced value above the inserted value.
    }

    public static long countSubsequences(int[] nums, int k) {
        return countFrom(nums, 0, 0L, false, k); // No index has been decided; no value chosen.
    }

    private static long countFrom(int[] nums, int index, long sum, boolean chosen, int k) {
        if (index == nums.length) { // Every index now has exactly one take/skip decision.
            return chosen && sum == k ? 1L : 0L; // Count one valid non-empty choice, or none.
        }
        long take = countFrom(nums, index + 1, sum + nums[index], true, k); // Choose this index.
        long skip = countFrom(nums, index + 1, sum, chosen, k); // Leave this index out.
        return take + skip; // Disjoint choices contribute separate counts, even for equal values.
    }

    public static long countSubsequencesDp(int[] nums, int k) {
        long[] ways = new long[k + 1]; // ways[s] counts choices from already processed indexes.
        ways[0] = 1; // One empty choice starts the construction; k is positive in this problem.
        for (int value : nums) { // Introduce each array position exactly once.
            for (int sum = k; sum >= value; sum--) { // Descend: do not reuse this value twice.
                ways[sum] += ways[sum - value]; // Add choices that become sum by taking value.
            }
        }
        return ways[k] - (k == 0 ? 1 : 0); // Exclude the empty choice in the teaching k=0 extension.
    }

    public static boolean hasSubsequence(int[] nums, int k) {
        return existsFrom(nums, 0, k); // remaining is the amount the undecided suffix must supply.
    }

    private static boolean existsFrom(int[] nums, int index, int remaining) {
        if (remaining == 0) return true; // A witness has already been found; further choices aren't needed.
        if (index == nums.length) return false; // No undecided values remain to close a nonzero gap.
        if (existsFrom(nums, index + 1, remaining - nums[index])) return true; // Take; stop on success.
        return existsFrom(nums, index + 1, remaining); // Try skipping only if taking failed.
    }

    public static boolean hasSubsequenceDp(int[] nums, int k) {
        boolean[] reachable = new boolean[k + 1]; // reachable[s] means processed indexes can form s.
        reachable[0] = true; // Choosing nothing forms zero; the actual target k is positive.
        for (int value : nums) { // Consider one new position at a time.
            for (int sum = k; sum >= value; sum--) { // Descend so each position is used at most once.
                reachable[sum] |= reachable[sum - value]; // Keep old witnesses or extend one with value.
            }
        }
        return reachable[k]; // Existence needs a boolean, not a frequency.
    }

    public static List<String> binaryStrings(int n) {
        List<String> answer = new ArrayList<>(); // Own immutable completed strings here.
        buildBinary(n, new StringBuilder(), answer); // Start with an empty path.
        return answer; // Zero-first exploration already gives lexicographic order.
    }

    private static void buildBinary(int n, StringBuilder path, List<String> answer) {
        if (path.length() == n) { // A string is complete only at the requested length.
            answer.add(path.toString()); // Copy the text; don't save a mutable builder reference.
            return; // Do not append beyond n characters.
        }
        boolean canUseOne = path.length() == 0 || path.charAt(path.length() - 1) != '1'; // Avoid 11.
        path.append('0'); // Zero is always safe and comes first lexicographically.
        buildBinary(n, path, answer); // Finish every string with this prefix before its sibling.
        path.deleteCharAt(path.length() - 1); // Restore the parent prefix after the zero branch.
        if (canUseOne) { // This check refers to the original parent prefix, not the temporary zero.
            path.append('1'); // Choose one only when it cannot create consecutive ones.
            buildBinary(n, path, answer); // Explore this legal second branch.
            path.deleteCharAt(path.length() - 1); // Undo one so the caller sees its own prefix again.
        }
    }

    public static List<String> palindromes(String s) {
        int[] halfCounts = new int[26]; // At first these are full lowercase-letter frequencies.
        for (char c : s.toCharArray()) halfCounts[c - 'a']++; // Count repeated letters by identity.
        String middle = ""; // Even lengths have no center character.
        int odd = 0; // More than one unpaired letter makes a palindrome impossible.
        for (int letter = 0; letter < 26; letter++) { // Examine all allowed character types.
            if (halfCounts[letter] % 2 == 1) { // This letter needs the unique center position.
                odd++; // Track how many different letters need that position.
                middle = String.valueOf((char) ('a' + letter)); // Save the candidate center.
            }
            halfCounts[letter] /= 2; // Each mirrored pair contributes one letter to the left half.
        }
        List<String> answer = new ArrayList<>(); // No output is a valid impossible-case result.
        if (odd > 1) return answer; // Two odd letters cannot both occupy the single center.
        permuteHalf(halfCounts, s.length() / 2, new StringBuilder(), middle, answer); // Generate only half.
        return answer; // Each unique half determines exactly one unique palindrome.
    }

    private static void permuteHalf(int[] counts, int length, StringBuilder left,
                                    String middle, List<String> answer) {
        if (left.length() == length) { // Every required left-half character has been placed.
            String right = new StringBuilder(left).reverse().toString(); // Mirror a copy, not shared left.
            answer.add(left.toString() + middle + right); // Assemble the full symmetric string.
            return; // No remaining position needs another choice.
        }
        for (int letter = 0; letter < 26; letter++) { // Branch by letter type, not identical occurrences.
            if (counts[letter] == 0) continue; // No copy of this letter remains for this position.
            counts[letter]--; // Reserve one copy for the current recursive branch.
            left.append((char) ('a' + letter)); // Extend this shared path by one character.
            permuteHalf(counts, length, left, middle, answer); // Solve the shorter remaining task.
            left.deleteCharAt(left.length() - 1); // Restore the path for the next letter choice.
            counts[letter]++; // Restore availability; siblings must start from the same inventory.
        }
    }

    // The judge supplies this API. The algorithm may not read fields or change next pointers.
    public interface ImmutableListNode {
        void printValue();
        ImmutableListNode getNext();
    }

    public static void printReverse(ImmutableListNode head) {
        if (head == null) return; // Beyond the final node there is nothing to print.
        printReverse(head.getNext()); // Print the entire suffix before printing this node.
        head.printValue(); // This suspended frame resumes after all later nodes were printed.
    }

    public static List<Integer> steppingNumbers(int low, int high) {
        List<Integer> answer = new ArrayList<>(); // Collect generated values that lie in the range.
        if (low == 0) answer.add(0); // Include zero once; never extend it into leading-zero numbers.
        for (int first = 1; first <= 9; first++) { // Each positive number has one nonzero first digit.
            extendStepping(first, low, high, answer); // Explore the tree rooted at that first digit.
        }
        Collections.sort(answer); // DFS order is not numeric order across roots or depths.
        return answer; // Return the sorted list, not its count.
    }

    private static void extendStepping(long number, int low, int high, List<Integer> answer) {
        if (number > high) return; // Appending a digit only increases this positive number.
        if (number >= low) answer.add((int) number); // Save this prefix only when it is in range.
        int last = (int) (number % 10); // Only the final digit constrains the next digit.
        if (last > 0) { // A digit below zero does not exist.
            extendStepping(number * 10 + last - 1, low, high, answer); // Append last-1 using long.
        }
        if (last < 9) { // A digit above nine does not exist.
            extendStepping(number * 10 + last + 1, low, high, answer); // Append last+1 using long.
        }
    }

    public static class TreeNode { // Local test model; use the judge's TreeNode in submissions.
        public int val;
        public TreeNode left, right;
        public TreeNode(int val) { this.val = val; }
    }

    public static TreeNode[] splitBst(TreeNode root, int target) {
        if (root == null) return new TreeNode[] {null, null}; // Two empty pieces split an empty subtree.
        if (root.val <= target) { // Root and its entire left subtree belong to the small result.
            TreeNode[] parts = splitBst(root.right, target); // Only the right subtree can straddle target.
            root.right = parts[0]; // Reattach its small piece; left remains untouched.
            return new TreeNode[] {root, parts[1]}; // Root is small; pass the large piece upward.
        }
        TreeNode[] parts = splitBst(root.left, target); // Root is large; only its left can straddle target.
        root.left = parts[1]; // Reattach the large left piece; right remains untouched.
        return new TreeNode[] {parts[0], root}; // Small piece comes first in the result contract.
    }
}
