Chouti is working on a strange math problem.

There was a sequence of $n$ positive integers $x_1, x_2, \ldots, x_n$, where $n$ is even. The sequence was very special, namely for every integer $t$ from $1$ to $n$, $x_1+x_2+...+x_t$ is a square of some integer number (that is, a perfect square).

Somehow, the numbers with odd indexes turned to be missing, so he is only aware of numbers on even positions, i.e. $x_2, x_4, x_6, \ldots, x_n$. The task for him is to restore the original sequence. Again, it's your turn to help him.

The problem setter might make mistakes, so there can be no possible sequence at all. If there are several possible sequences, you can output any.


-----Input-----

The first line contains an even number $n$ ($2 \le n \le 10^5$).

The second line contains $\frac{n}{2}$ positive integers $x_2, x_4, \ldots, x_n$ ($1 \le x_i \le 2 \cdot 10^5$).


-----Output-----

If there are no possible sequence, print "No".

Otherwise, print "Yes" and then $n$ positive integers $x_1, x_2, \ldots, x_n$ ($1 \le x_i \le 10^{13}$), where $x_2, x_4, \ldots, x_n$ should be same as in input data. If there are multiple answers, print any.

Note, that the limit for $x_i$ is larger than for input data. It can be proved that in case there is an answer, there must be a possible sequence satisfying $1 \le x_i \le 10^{13}$.


-----Examples-----
Input
6
5 11 44

Output
Yes
4 5 16 11 64 44

Input
2
9900

Output
Yes
100 9900

Input
6
314 1592 6535

Output
No



-----Note-----

In the first example   $x_1=4$  $x_1+x_2=9$  $x_1+x_2+x_3=25$  $x_1+x_2+x_3+x_4=36$  $x_1+x_2+x_3+x_4+x_5=100$  $x_1+x_2+x_3+x_4+x_5+x_6=144$  All these numbers are perfect squares.

In the second example, $x_1=100$, $x_1+x_2=10000$. They are all perfect squares. There're other answers possible. For example, $x_1=22500$ is another answer.

In the third example, it is possible to show, that no such sequence exists.

Difficulty: interview

Starter code:

Solutions:
Z = 100000

n = int(input())
xx = list(map(int, input().split()))


def cal():
    ans = []
    a = 1
    b = 1
    s = 0
    ls = 1
    for x in xx:
        while b <= Z:
            if s < x:
                s += b * 2 + 1
                b += 1
            elif s > x:
                s -= a * 2 + 1
                ls += a * 2 + 1
                a += 1
            else:
                ans.append(ls)
                ans.append(x)
                ls = b * 2 + 1
                b += 1
                a = b
                s = 0
                break
        else:
            return
    return ans


ans = cal()
if ans:
    print('Yes')
    print(' '.join(map(str, ans)))
else:
    print('No')


import math
n=int(input())
a=list(map(int,input().split()))
r=lambda y:int(math.sqrt(y))
def R(x):
 y=r(x)
 return y*y==x
z=0
b=[]
for i in a:
 f=0
 for q in range(r(z)+1,3160000):
  y=q*q-z;
  if R(q*q+i):
   b+=[y,i];z+=i+y;f=1;break
 if f<1:
  print('No');return
print('Yes\n',*b)

import sys
import math

n=int(input())
A=list(map(int,input().split()))


ANS=[None]*(n//2+1)
ANS[0]=[0,0]

for i in range(n//2):
    NEXT=[]

    #x**2=?
    #y**2=A[i//2]

    z=A[i]
        
    xr=math.ceil(math.sqrt(z))

    LIST=[]
    for j in range(1,xr+1):
        if z%j==0:
            LIST.append(j)
    #print(LIST)

    for l in LIST[::-1]:
        if (l+z//l)%2==1:
            continue
        y=(l+z//l)//2
        x=y-l
        #print(x,y)

        _,N=ANS[i]
        if x**2>N:
            NEXT=[x**2,y**2]
            break
        

    #print(NEXT)
    if NEXT==[]:
        print("No")
        return

    ANS[i+1]=NEXT


#print(ANS)

print("Yes")
for i in range(1,n//2+1):
    print(ANS[i][0]-ANS[i-1][1],end=" ")
    print(ANS[i][1]-ANS[i][0],end=" ")
    
    
                
                

            
            

        
        


import math
n=int(input())
x=list(map(int,input().split()))
currsum=0
others=[]
done=False
for i in range(n//2):
    a=x[i]
    sml=None
    big=None
    if a%4==2:
        print("No")
        done=True
        break
    elif a%2==1:
        for i in range(1,math.ceil(-currsum+(currsum**2+a)**0.5),2):
            if a%i==0:
                sml=((a-i**2)//(2*i))**2
                big=sml+a
    else:
        for i in range(2,math.ceil(-currsum+(currsum**2+a)**0.5),2):
            if a%(2*i)==0:
                sml=((a-i**2)//(2*i))**2
                big=sml+a
    if sml==None:
        print("No")
        done=True
        break
    others.append(sml-int(currsum)**2)
    currsum=big**0.5
if not done:
    out=""
    for i in range(n//2):
        out+=str(others[i])+" "+str(x[i])+" "
    print("Yes")
    print(out[:-1])

# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 12/20/18

"""

import collections
import time
import os
import sys
import bisect
import heapq
import bisect


S = 2 * 10**5 + 5
V = collections.defaultdict(list)
for i in range(1, S+1):
    if 2*i+1 > S:
        break
    
    j = i + 1
    while j*j-i*i <= S:
        V[j*j-i*i].append((i, j))
        j += 1


N = int(input())
X = [int(x) for x in input().split()]
ans = [0] * (N+1)
xi = 0
for i in range(2, N+1, 2):
    x = X[xi]
    xi += 1
    for v in V[x]:
        if ans[i-2] < v[0]:
            ans[i-1] = v[0]
            ans[i] = v[1]
            break
            
    if ans[i-1] == 0:
        print('No')
        return
print('Yes')

print(' '.join(map(str, [ans[i]**2-ans[i-1]**2 for i in range(1, N+1)])))



import math

n = int(input())
cl = list(map(int, input().split()))
sm = 0


def func(p, q):
  if q%2!=0 or q%4==0:
    for i in range(int(math.sqrt(q)), 0, -1):
      if q%i==0 and (i+q//i)%2==0:
        k = ((q//i-i)//2)**2
        if k>p:
          return k-p
    return -1
  else:
    return -1

res = []

for i in range(n//2):
  e = func(sm, cl[i])
  if e == -1:
    print('No')
    return
  res.append(e)
  res.append(cl[i])
  sm+=e+cl[i]

print('Yes')
print(*res)

from sys import stdin,stdout
from itertools import combinations
from collections import defaultdict,OrderedDict
import math
import heapq

def listIn():
    return list((list(map(int,stdin.readline().strip().split()))))

def stringListIn():
    return([x for x in stdin.readline().split()])
    
def intIn():
    return (int(stdin.readline()))

def stringIn():
    return (stdin.readline().strip())

def perfectSquare(k):
    s=math.sqrt(k)
    if s-int(s)==0:
        return 1
    else:
        return 0

def check(a,b,op,i):
    e1,e2=a,b
    if op=="-":
        diff=e2-e1
    else:
        diff=e2+e1
    if perfectSquare(diff):
        #print(diff)
        if diff-arr[i-1]>0 or i==0:
            arr[i]=diff
            arr[i+1]=e2
            return 1
        else:
            return 0
    else:
        return 0
            
    
def __starting_point():
    n=intIn()
    even=listIn()
    arr=[0]*n
    j=0
    for i in range(n):
        if i%2!=0:
            arr[i]=even[j]
            j+=1
    
    k=0     #arr[0]+...arr[i] =k*k      current sum
    l=0    #arr[0]+...arr[i+1] =l*l     forward sum
    s=0     #arr[0]+...arr[i-1] =s        previous sum
    
    zcnt=0
    b_end=10**13
    flag=False
    for i in range(0,n,2):
        found=False
        while(not found):
            k+=1
            if (k*k-s>b_end):
                print('No')
                return
            #given current sum=k^2
            #then checking if k*k+arr[i+1]=l^2
            forward_sum=k*k+arr[i+1]
            while(forward_sum>l*l):
                l+=1
            if forward_sum==l*l:
                found=True
                arr[i]=k*k-s
                s=forward_sum
                k=l
        #print(arr,s)
    print('Yes')
    print(*arr)
                    

                    
        

__starting_point()

def bi(a, x):
    l  = -1
    u  = len(a)
    
    while(u-l>1):
        md = int((l+u) / 2)
        if x >= a[md]:
            l = md
        else:
            u = md
    return u  

d = {}
for x in range(1, 100000):
    
    for a in range(1, 500):
        diff = a*a + 2*a*x
        
        if diff > 200000:
            break
        
        if diff  not in d:
            d[diff] = []
            
        d[diff].append(x*x)    
        
def solve(a, d):
    cur = 0
    ans = ''
    
    for x in a:
        if x not in d:
            return 'No', ''
        
        next_ = bi(d[x], cur)
        
        if next_ == len(d[x]): 
            return 'No', ''
        
        next_ = d[x][next_]
        ans  +=  str(next_ - cur) + ' ' + str(x) +' '
        cur = next_ + x 
    
    return 'Yes', ans

n   = int(input())
a   = list(map(int, input().split()))
ans = solve(a, d)

print(ans[0])
print(ans[1])

'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College
    Date:10/06/2020

'''
from os import path
import sys
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return list(map(int,input().split()))
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')

def check(x):
    x1=int(sqrt(x))
    return x1*x1==x
def solve():
    
    # for _ in range(ii()):
        
        
        
    n=ii()
    a=li()
    tmp=[0]*n
    tot=0
    x=1
    for i in range(n//2):
        tmp[2*i+1]=a[i]
        while(x<1000000):
            if x*x>tot and check(x*x+a[i]):
                tmp[2*i]=x*x-tot
                break
            x+=1
        if(x==1000000):
            print('No')
            return
        tot+=tmp[2*i]+a[i]
    print('Yes')
    print(*tmp)
    
        
        
        
        
def __starting_point():
    solve()

__starting_point()