Sorted squares

Problem

Temperature changes are listed in non-decreasing order and may be negative. Print the squares of the values in non-decreasing order. Use two pointers; do not call sort.

Input, output and limits

Input: One line of integers in non-decreasing order, separated by spaces.
Output: The squares in non-decreasing order, separated by spaces.
Constraints: 1 ≤ count ≤ 100000
-10000 ≤ each value ≤ 10000

Examples

Example

Input

-7 -3 2 3 11

Output

4 9 9 49 121

Hints

Try the problem first. Open one hint at a time.

Hint 1

The largest square is at one of the two ends.

Hint 2

Fill the answer from the back with the larger square and move the pointer that supplied it.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Unique values of a sorted listeasy
Merge two sorted listseasy
Zeros to the backeasy
Container with the most watermedium
Reverse the order listeasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Two Pointers problems

Problem

Input, output and limits

Examples

Hints

More Two Pointers problems