Cram Time
Contest: Technocup 2019 - Elimination Round 2
Difficulty rating: 1600
Tags: greedy

In a galaxy far, far away Lesha the student has just got to know that he has an exam in two days. As always, he hasn't attended any single class during the previous year, so he decided to spend the remaining time wisely.

Lesha knows that today he can study for at most $$$a$$$ hours, and he will have $$$b$$$ hours to study tomorrow. Note that it is possible that on his planet there are more hours in a day than on Earth. Lesha knows that the quality of his knowledge will only depend on the number of lecture notes he will read. He has access to an infinite number of notes that are enumerated with positive integers, but he knows that he can read the first note in one hour, the second note in two hours and so on. In other words, Lesha can read the note with number $$$k$$$ in $$$k$$$ hours. Lesha can read the notes in arbitrary order, however, he can't start reading a note in the first day and finish its reading in the second day.

Thus, the student has to fully read several lecture notes today, spending at most $$$a$$$ hours in total, and fully read several lecture notes tomorrow, spending at most $$$b$$$ hours in total. What is the maximum number of notes Lesha can read in the remaining time? Which notes should he read in the first day, and which — in the second?

Input format:
The only line of input contains two integers $$$a$$$ and $$$b$$$ ($$$0 \leq a, b \leq 10^{9}$$$) — the number of hours Lesha has today and the number of hours Lesha has tomorrow.

Output format:
In the first line print a single integer $$$n$$$ ($$$0 \leq n \leq a$$$) — the number of lecture notes Lesha has to read in the first day. In the second line print $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq a$$$), the sum of all $$$p_i$$$ should not exceed $$$a$$$.

In the third line print a single integer $$$m$$$ ($$$0 \leq m \leq b$$$) — the number of lecture notes Lesha has to read in the second day. In the fourth line print $$$m$$$ distinct integers $$$q_1, q_2, \ldots, q_m$$$ ($$$1 \leq q_i \leq b$$$), the sum of all $$$q_i$$$ should not exceed $$$b$$$.

All integers $$$p_i$$$ and $$$q_i$$$ should be distinct. The sum $$$n + m$$$ should be largest possible.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example Lesha can read the third note in $$$3$$$ hours in the first day, and the first and the second notes in one and two hours correspondingly in the second day, spending $$$3$$$ hours as well. Note that Lesha can make it the other way round, reading the first and the second notes in the first day and the third note in the second day.

In the second example Lesha should read the third and the sixth notes in the first day, spending $$$9$$$ hours in total. In the second day Lesha should read the first, second fourth and fifth notes, spending $$$12$$$ hours in total.

Example input:
3 3

Example output:
1
3
2
2 1

Example input:
9 12

Example output:
2
3 6
4
1 2 4 5

Editorial:
Consider any answer with maximal $$$n + m$$$. If we used numbers $$$d_1, d_2, \ldots, d_k$$$ ($$$d_i \gt n + m$$$), then we didn't use some numbers $$$h_1, h_2, \ldots, h_k$$$ ($$$h_i \leq n + m$$$). Replacing all $$$d_i$$$ by $$$h_i$$$ ($$$1 \leq i \leq k$$$) doesn't violate the restriction. That means that we can assume that the answer consists of all numbers from $$$1$$$ to $$$x$$$, and $$$x = n + m$$$. The sum of all numbers from $$$1$$$ to $$$x$$$ equals $$$\frac{x(x + 1)}{2}$$$. It's clear that the following inequality must hold: $$$\frac{x(x + 1)}{2} \leq a + b$$$. Let's find the maximal $$$x$$$ for which it's true. The answer can't exceed $$$x$$$, and we can build the answer for $$$x$$$ iteratively. Let's iterate over all lecture notes from $$$x$$$ to $$$1$$$, and on each step we put it into the first day if we can, otherwise if in the first day we have $$$w > 0$$$ free time then we put the lecture note $$$w < x$$$ to the first day. All other lecture notes can be read during the second day since the either there are none of them, or the first day is full and hence the second day contains a sufficient amount of hours to read'em all.