Numbers

Time limit1sMemory limit1024 MB

Summary

Given N positive integers, their total sum, and the products of each adjacent pair, find the integers or report that none exist.

Level: Medium6 of 10
Topics: Number theory, Math, Implementation
Solved: No attempts yet

Problem

Vytautas has lived in England for a long time and spends his free time on math puzzles. One day a friend gave him this problem: there are 10 positive integers. Given their sum and the products of the first and second, second and third, ..., ninth and tenth numbers, find the numbers. Vytautas solved it on paper in half an hour.

The next day his friend gave him the same problem with 100 numbers. Then Vytautas realized that it would be simpler to write a program that solves this problem for $N$ numbers.

Given $N$ , the sum of all numbers, and the products of the first and second, second and third, ..., $(N-1)$ -th and $N$ -th numbers, find the numbers themselves, if such numbers exist.

Input

The first line contains $N$ . The second line contains the sum of all numbers. The third line contains the product of the first and second numbers, the fourth line the product of the second and third numbers, and so on, until line $N+1$ , which contains the product of the $(N-1)$ -th and $N$ -th numbers.

Output

If such numbers exist, print TAIP on the first line. Print the first number on the second line, the second number on the third line, and so on, with the $N$ -th number on the last line. If there are several correct answers, print any of them.

If no numbers satisfy the data, print NE on the only line.

Constraints

For all tests, $2 \le N \le 20000$ . The sum and the products given in the statement are positive integers not exceeding $10^9$ .

Examples3

Example 1
Input
```
2
5
6
```
Expected output
```
TAIP
2
3
```
Example 2
Input
```
4
26
23
23
1
```
Expected output
```
TAIP
1
23
1
1
```
Example 3
Input
```
4
5
1
1
1
```
Expected output
```
NE
```