Відновлення префіксів і суфіксів (Розбір)

Рішення

Давайте побудуємо масив $a$ за різницею між $p$ і $s$. Загалом, нехай $x$ буде побудовою масиву $a$ на основі $p$, а $y$ — побудовою масиву $a$ на основі $s$. Нехай x_1=a_1 і

для кожного (1 \le i \le n-1). Те ж саме стосується суфіксної суми, y_n=s_1 і

В кінці нашої побудови, якщо x=y, то існує валідний $a$, і це правильно, і ми вважаємо це.

for _ in range(int(input())):
    n=int(input())
    p=list(map(int,input().split()))
    s=list(map(int,input().split()))
    a=[0]*n
    b=[0]*n
    a[0]=p[0]
    b[n-1]=s[0]
    for i in range(1,n):
        a[i]=p[i]-p[i-1]
        b[n-1-i]=s[i]-s[i-1]
    if(a==b):
        print(*a)
    else:
        print(-1)

Складність $\mathcal{O}(n)$.