Divide Recipes

You are given a list of integers representing the preparation times for various recipes. Your task is to divide these recipes between two chefs such that the total preparation times are as evenly balanced as possible.

In other words, partition the list into two sublists where the absolute difference between the sum of the two sublists is minimized. The order of recipes within each sublist does not matter; however, for the purpose of obtaining a unique output for verification, you should output each sublist in ascending order.

Note: There may be multiple valid answers; however, your solution should follow the processing method described below to ensure consistency.

Hint: A dynamic programming approach can be used to determine a subset with a sum close to \(\frac{\text{total sum}}{2}\).

inputFormat

The first line contains an integer \(n\) representing the number of recipes. The second line contains \(n\) space-separated integers indicating the preparation times of the recipes.

outputFormat

Output two lines. The first line should contain the preparation times assigned to the first chef (in ascending order), and the second line should contain the preparation times assigned to the second chef (in ascending order). Each number must be separated by a space.

## sample

5
10 20 30 40 50

20 50
10 30 40

</p>