Remove 0 sum subarrays

Given n integers, you are asked to remove all the contiguous subarrays that sum up to 0. You should start from the start of the array and move to the end of it, and as soon as a 0-sum-subarray is found, you should remove it from the array.

Input

The first line of the input contains a single integer n (1 ≀ n ≀ ).
The next line contains n space-separated integers ( ≀ ≀ ).

Output

The program should print the resulting array after removing all the subarrays that sum up to 0.

Examples

Input
Output
8 5 -5 8 6 -14 9 9 -9
9
11 4 7 -11 8 7 10 -18 10 -17 20 25
20 25

Explanation

  1. Remove [5, -5], [8, 6, -14], and [9, -9]
  1. Remove [4 7 -11] and [8 7 10 -18 10 -17]
Β 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue