Two Sets of Cards
Source: aizu

Problem G
Two Sets of Cards

As an entertainment after the programming contest, you hold a game event for the participants.

Two sets of cards, red ones and blue ones, are used in the game. Both of the two sets have the same number of cards as the number of the participants, and each card has one integer written on it. It is known that the contents of these two sets are the same; the integers on the red cards are the same as those on the blue cards as multisets. Even though, you don't know what integers are actually written on the cards. The same integer may be written on two or more cards of the same color, and the integers may be negative.

You distributed one red card and one blue card to each of the participants. As the game result depends on the sum of the integers on the two cards distributed to each participant, you asked all the participants to declare their sums.

Your task is to find a possible card distribution consistent with the participants' declarations, that is, a combination of integers on the cards distributed to each participant. Note that such a combination might not exist, as the participants may commit miscalculations. In such a case, report that there is no consistent combination.

Input

The input consists of multiple datasets, each in the following format. The number of datasets does not exceed 100.

n
s1 s2 ⋯ sn


Here, n is the number of the participants, an integer between 1 and 70, inclusive. Each of si (i = 1, , n) is the declared sum of the integers on the two cards distributed to the i-th participant, an integer between −150 and 150, inclusive.

The end of the input is indicated by a line consisting of a zero.

Output

For each dataset, if there exists no combination of integers on the cards distributed to each participant that is consistent with the participants' declarations, output "No" in one line. Otherwise, output "Yes" in one line followed by one possible consistent combination in the following format.

a1 a2 ⋯ an 
b1 b2 ⋯ bn 


Here, for i = 1, , n, ai and bi represent the integers on the red and blue cards, respectively, distributed to the i-th participant. Each of ai and bi must be an integer between −109 and 109, inclusive. It can be proved that, when one or more consistent combinations exist, there also exists a consistent combination satisfying this condition. If there are two or more such combinations, you may output any one of them.

Sample Input
3
7 -2 3
3
4 8 8
4
1 2 4 8
6
-6 -2 3 2 9 -4
1
-100
0

Output for the Sample Input
Yes
1 -3 6
6 1 -3
Yes
2 4 4
2 4 4
No
Yes
3 -1 4 -1 5 -9
-9 -1 -1 3 4 5
Yes
-50
-50


C++ solution:
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    
    auto solve = [&]() {
        vector<int> s(n), a(n), b(n);
        for (int i = 0; i < n; i++) {
            cin >> s[i];
        }

        vector pos(2, vector<int>());
        for (int i = 0; i < n; i++) {
            pos[abs(s[i]) % 2].push_back(i);
        }

        if (pos[1].size() % 2 == 1) {
            cout << "No\n";
            return;
        } else if (!pos[0].empty()) {
            int e = pos[0].back();
            pos[0].pop_back();
            pos[1].push_back(e);
            for (int i : pos[0]) {
                a[i] = b[i] = s[i] / 2;
            }
            int z = 0;
            for (int i : pos[1]) {
                z += s[i];
            }
            assert(z % 2 == 0);
            z /= 2;
            int sz = pos[1].size();
            for (int i = 0; i < sz; i++) {
                if (i == 0) {
                    for (int k = 0; k < sz; k += 2) {
                        a[pos[1][i]] += s[pos[1][k]];
                    }
                    a[pos[1][i]] -= z;
                } else {
                    a[pos[1][i]] = s[pos[1][i - 1]] - a[pos[1][i - 1]];
                }
            }
            for (int i = 0; i < sz; i++) {
                b[pos[1][i]] = a[pos[1][(i + 1) % sz]];
            }
        } else {
            int sz = pos[1].size();
            const int V = 150, S = V * sz / 2;
            vector dp(sz + 1, vector(sz + 1, vector<int>(2 * S + 1)));
            dp[0][0][S] = true;
            for (int i = 0; i < sz; i++) {
                int v = s[pos[1][i]];
                for (int j = 0; j <= i; j++) {
                    for (int k = 0; k <= 2 * S; k++) {
                        if (dp[i][j][k]) {
                            if (0 <= k + v && k + v <= 2 * S) {
                                dp[i + 1][j + 1][k + v] = true;
                            }
                            if (0 <= k - v && k - v <= 2 * S) {
                                dp[i + 1][j][k - v] = true;
                            }
                        }
                    }
                }
            }
            if (!dp[sz][sz / 2][S]) {
                cout << "No\n";
                return;
            }
            vector part(2, vector<int>());
            for (int i = sz - 1, j = sz / 2, k = S; i >= 0; i--) {
                int v = s[pos[1][i]];
                if (0 <= k - v && k - v <= 2 * S && j > 0 && dp[i][j - 1][k - v]) {
                    j--;
                    k -= v;
                    part[0].push_back(pos[1][i]);
                } else if (0 <= k + v && k + v <= 2 * S && dp[i][j][k + v]) {
                    k += v;
                    part[1].push_back(pos[1][i]);
                } else {
                    assert(false);
                }
            }
            assert(part[0].size() == part[1].size() && part[0].size() == sz / 2);
            for (int i = 0; i < sz; i++) {
                pos[1][i] = part[i % 2][i / 2];
            }
            for (int i = 1; i < sz; i++) {
                a[pos[1][i]] = s[pos[1][i - 1]] - a[pos[1][i - 1]];
            }
            for (int i = 0; i < sz; i++) {
                b[pos[1][i]] = a[pos[1][(i + 1) % sz]];
            }
        }

        cout << "Yes\n";
        for (int i = 0; i < n; i++) {
            cout << a[i] << " \n"[i + 1 == n];
        }
        for (int i = 0; i < n; i++) {
            cout << b[i] << " \n"[i + 1 == n];
        }
        #ifdef LOCAL
        for (int i = 0; i < n; i++) {
            assert(a[i] + b[i] == s[i]);
        }
        assert(multiset<int>(a.begin(), a.end()) == multiset<int>(b.begin(), b.end()));
        #endif
    };

    while (cin >> n && n != 0) {
        solve();
    }

    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

const inf = 1 << 60

type pair struct {
	first  int
	second int
}

func calc1(res []pair) ([]int, []int) {
	s := 0
	for _, p := range res {
		s += p.first
	}
	s /= 2
	m := len(res)
	for i := 1; i < m; i += 2 {
		s -= res[i].first
	}
	ans := []int{s}
	for i := 0; i < m-1; i++ {
		ns := res[i].first - s
		ans = append(ans, ns)
		s = ns
	}
	ans2 := append(ans[1:], ans[0])
	return ans, ans2
}

func calc2(a []int) ([]int, []int) {
	n := len(a)
	if n%2 != 0 {
		return make([]int, n), make([]int, n)
	}

	type state struct {
		sm, s1, s2 int
	}
	dp := make([]map[state]bool, n+1)
	for i := range dp {
		dp[i] = make(map[state]bool)
	}
	dp[0][state{0, 0, 0}] = true

	for i := 0; i < n; i++ {
		for s := range dp[i] {
			if s.s1+1 <= n/2 {
				newState := state{s.sm + a[i], s.s1 + 1, s.s2}
				dp[i+1][newState] = true
			}
			if s.s2+1 <= n/2 {
				newState := state{s.sm - a[i], s.s1, s.s2 + 1}
				dp[i+1][newState] = true
			}
		}
	}

	ans1 := make([]int, n)
	ans2 := make([]int, n)
	for i := range ans1 {
		ans1[i] = -inf
		ans2[i] = -inf
	}

	target := state{0, n / 2, n / 2}
	if !dp[n][target] {
		return ans1, ans2
	}

	sm, s1, s2 := 0, n/2, n/2
	var p0, p1 []int

	for i := n - 1; i >= 0; i-- {
		s := state{sm - a[i], s1 - 1, s2}
		if dp[i][s] {
			p0 = append(p0, i)
			sm -= a[i]
			s1--
		} else {
			p1 = append(p1, i)
			sm += a[i]
			s2--
		}
	}

	// Reverse p0 and p1
	for i, j := 0, len(p0)-1; i < j; i, j = i+1, j-1 {
		p0[i], p0[j] = p0[j], p0[i]
	}
	for i, j := 0, len(p1)-1; i < j; i, j = i+1, j-1 {
		p1[i], p1[j] = p1[j], p1[i]
	}

	var perm []int
	for i := 0; i < n/2; i++ {
		perm = append(perm, p0[i])
		perm = append(perm, p1[i])
	}

	A := make([]int, n)
	for i, idx := range perm {
		A[i] = a[idx]
	}

	X := []int{0}
	s := 0
	for _, num := range A {
		ns := num - s
		X = append(X, ns)
		s = ns
	}

	for i := 0; i < n; i++ {
		ans1[perm[i]] = X[i+1]
		ans2[perm[(i+1)%n]] = X[i+1]
	}

	// Additional verification step
	valid := true
	for i := 0; i < n; i++ {
		if ans1[i]+ans2[i] != a[i] {
			valid = false
			break
		}
	}
	if !valid {
		return make([]int, n), make([]int, n)
	}

	return ans1, ans2
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	for {
		var n int
		scanner.Scan()
		n, _ = strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}

		scanner.Scan()
		fields := strings.Fields(scanner.Text())
		a := make([]int, n)
		sum := 0
		for i := 0; i < n; i++ {
			a[i], _ = strconv.Atoi(fields[i])
			sum += a[i]
		}

		if sum%2 == 1 {
			fmt.Println("No")
			continue
		}

		var even []pair
		var odd []pair
		for i := 0; i < n; i++ {
			if a[i]%2 == 0 {
				even = append(even, pair{a[i], i})
			} else {
				odd = append(odd, pair{a[i], i})
			}
		}

		if len(even) > 0 {
			res := append([]pair{even[0]}, odd...)
			ans1, ans2 := calc1(res)
			B := make([]int, n)
			C := make([]int, n)
			for i := 0; i < n; i++ {
				B[i] = -inf
				C[i] = -inf
			}
			for i := 0; i < len(res); i++ {
				idx := res[i].second
				B[idx] = ans1[i]
				C[idx] = ans2[i]
			}
			for i := 0; i < n; i++ {
				if B[i] == -inf {
					B[i] = a[i] / 2
					C[i] = a[i] / 2
				}
			}
			// Verify the solution
			valid := true
			for i := 0; i < n; i++ {
				if B[i]+C[i] != a[i] {
					valid = false
					break
				}
			}
			if !valid {
				fmt.Println("No")
				continue
			}
			fmt.Println("Yes")
			for i := 0; i < n; i++ {
				if i > 0 {
					fmt.Print(" ")
				}
				fmt.Print(B[i])
			}
			fmt.Println()
			for i := 0; i < n; i++ {
				if i > 0 {
					fmt.Print(" ")
				}
				fmt.Print(C[i])
			}
			fmt.Println()
			continue
		}

		if n%2 != 0 {
			fmt.Println("No")
			continue
		}

		ans1, ans2 := calc2(a)
		if ans1[0] == -inf {
			fmt.Println("No")
		} else {
			// Verify the solution
			valid := true
			for i := 0; i < n; i++ {
				if ans1[i]+ans2[i] != a[i] {
					valid = false
					break
				}
			}
			if !valid {
				fmt.Println("No")
			} else {
				fmt.Println("Yes")
				for i := 0; i < n; i++ {
					if i > 0 {
						fmt.Print(" ")
					}
					fmt.Print(ans1[i])
				}
				fmt.Println()
				for i := 0; i < n; i++ {
					if i > 0 {
						fmt.Print(" ")
					}
					fmt.Print(ans2[i])
				}
				fmt.Println()
			}
		}
	}
}

Java solution:
import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 1 << 30;

    static class Pair {
        int first, second;
        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    static List<Integer> calc1(List<Pair> res) {
        int s = 0;
        for (Pair p : res) {
            s += p.first;
        }
        s /= 2;
        int m = res.size();
        for (int i = 1; i < m; i += 2) {
            s -= res.get(i).first;
        }
        List<Integer> ans = new ArrayList<>();
        ans.add(s);
        for (int i = 0; i < m - 1; i++) {
            int ns = res.get(i).first - ans.get(ans.size() - 1);
            ans.add(ns);
        }
        return ans;
    }

    static int[][] calc2(int[] a) {
        int n = a.length;
        Set<Triple>[] dp = new HashSet[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = new HashSet<>();
        }
        dp[0].add(new Triple(0, 0, 0));
        for (int i = 0; i < n; i++) {
            for (Triple t : dp[i]) {
                if (t.s1 + 1 <= n / 2) {
                    dp[i + 1].add(new Triple(t.sm + a[i], t.s1 + 1, t.s2));
                }
                if (t.s2 + 1 <= n / 2) {
                    dp[i + 1].add(new Triple(t.sm - a[i], t.s1, t.s2 + 1));
                }
            }
        }
        int[][] result = new int[2][n];
        Arrays.fill(result[0], -INF);
        Arrays.fill(result[1], -INF);
        boolean found = false;
        Triple target = null;
        for (Triple t : dp[n]) {
            if (t.sm == 0 && t.s1 == n / 2 && t.s2 == n / 2) {
                found = true;
                target = t;
                break;
            }
        }
        if (!found) {
            return result;
        }
        int sm = target.sm;
        int s1 = target.s1;
        int s2 = target.s2;
        List<Integer> p0 = new ArrayList<>();
        List<Integer> p1 = new ArrayList<>();
        for (int i = n - 1; i >= 0; i--) {
            Triple t = new Triple(sm - a[i], s1 - 1, s2);
            if (s1 > 0 && dp[i].contains(t)) {
                p0.add(i);
                sm -= a[i];
                s1--;
            } else {
                t = new Triple(sm + a[i], s1, s2 - 1);
                p1.add(i);
                sm += a[i];
                s2--;
            }
        }
        Collections.reverse(p0);
        Collections.reverse(p1);
        List<Integer> perm = new ArrayList<>();
        for (int i = 0; i < n / 2; i++) {
            perm.add(p0.get(i));
            perm.add(p1.get(i));
        }
        List<Integer> X = new ArrayList<>();
        X.add(0);
        int s = 0;
        for (int idx : perm) {
            int ns = a[idx] - s;
            X.add(ns);
            s = ns;
        }
        for (int i = 0; i < n; i++) {
            int pos = perm.get(i);
            result[0][pos] = X.get(i + 1);
            result[1][perm.get((i + 1) % n)] = X.get(i + 1);
        }
        return result;
    }

    static class Triple {
        int sm, s1, s2;
        Triple(int sm, int s1, int s2) {
            this.sm = sm;
            this.s1 = s1;
            this.s2 = s2;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Triple triple = (Triple) o;
            return sm == triple.sm && s1 == triple.s1 && s2 == triple.s2;
        }

        @Override
        public int hashCode() {
            return Objects.hash(sm, s1, s2);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        while (true) {
            String line = br.readLine();
            if (line == null || line.isEmpty()) {
                continue;
            }
            int n = Integer.parseInt(line.trim());
            if (n == 0) {
                break;
            }
            line = br.readLine();
            String[] tokens = line.trim().split("\\s+");
            int[] a = new int[n];
            int sum = 0;
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(tokens[i]);
                sum += a[i];
            }
            if (sum % 2 != 0) {
                out.println("No");
                continue;
            }
            List<Pair> even = new ArrayList<>();
            List<Pair> odd = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (a[i] % 2 == 0) {
                    even.add(new Pair(a[i], i));
                } else {
                    odd.add(new Pair(a[i], i));
                }
            }
            if (!even.isEmpty()) {
                List<Pair> res = new ArrayList<>();
                res.add(even.get(0));
                res.addAll(odd);
                List<Integer> ans1 = calc1(res);
                List<Integer> ans2 = new ArrayList<>(ans1.subList(1, ans1.size()));
                ans2.add(ans1.get(0));
                int[] B = new int[n];
                int[] C = new int[n];
                Arrays.fill(B, -INF);
                Arrays.fill(C, -INF);
                for (int i = 0; i < res.size(); i++) {
                    int idx = res.get(i).second;
                    B[idx] = ans1.get(i);
                    C[idx] = ans2.get(i);
                }
                for (int i = 0; i < n; i++) {
                    if (B[i] == -INF) {
                        B[i] = a[i] / 2;
                        C[i] = a[i] / 2;
                    }
                }
                out.println("Yes");
                for (int i = 0; i < n; i++) {
                    out.print(B[i] + " ");
                }
                out.println();
                for (int i = 0; i < n; i++) {
                    out.print(C[i] + " ");
                }
                out.println();
            } else {
                int[][] ans = calc2(a);
                if (ans[0][0] == -INF) {
                    out.println("No");
                } else {
                    out.println("Yes");
                    for (int i = 0; i < n; i++) {
                        out.print(ans[0][i] + " ");
                    }
                    out.println();
                    for (int i = 0; i < n; i++) {
                        out.print(ans[1][i] + " ");
                    }
                    out.println();
                }
            }
        }
        out.flush();
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

const INF = 1 << 30;

function calc1(res) {
  let s = 0;
  for (const item of res) {
    s += item[0];
  }
  s = Math.floor(s / 2);
  const m = res.length;
  for (let i = 1; i < m; i += 2) {
    s -= res[i][0];
  }
  const ans = [s];
  for (let i = 0; i < m - 1; i++) {
    const ns = res[i][0] - ans[ans.length - 1];
    ans.push(ns);
  }
  const ans2 = [...ans.slice(1), ans[0]];
  return [ans, ans2];
}

function calc2(a) {
  const n = a.length;
  let dp = Array.from({ length: n + 1 }, () => new Set());
  dp[0].add(JSON.stringify([0, 0, 0]));

  for (let i = 0; i < n; i++) {
    for (const state of dp[i]) {
      const [sm, s1, s2] = JSON.parse(state);
      if (s1 + 1 <= n / 2) {
        dp[i + 1].add(JSON.stringify([sm + a[i], s1 + 1, s2]));
      }
      if (s2 + 1 <= n / 2) {
        dp[i + 1].add(JSON.stringify([sm - a[i], s1, s2 + 1]));
      }
    }
  }

  const ans1 = Array(n).fill(-INF);
  const ans2 = Array(n).fill(-INF);
  const target = JSON.stringify([0, n / 2, n / 2]);
  if (!dp[n].has(target)) {
    return [ans1, ans2];
  }

  let sm = 0, s1 = n / 2, s2 = n / 2;
  const p0 = [];
  const p1 = [];

  for (let i = n - 1; i >= 0; i--) {
    const state = JSON.stringify([sm - a[i], s1 - 1, s2]);
    if (dp[i].has(state)) {
      p0.push(i);
      sm -= a[i];
      s1 -= 1;
    } else {
      p1.push(i);
      sm += a[i];
      s2 -= 1;
    }
  }

  p0.reverse();
  p1.reverse();

  const perm = [];
  for (let i = 0; i < n / 2; i++) {
    perm.push(p0[i]);
    perm.push(p1[i]);
  }

  const A = perm.map(i => a[i]);
  const X = [0];
  let current = 0;
  for (const num of A) {
    const ns = num - current;
    X.push(ns);
    current = ns;
  }

  for (let i = 0; i < n; i++) {
    ans1[perm[i]] = X[i + 1];
    ans2[perm[(i + 1) % n]] = X[i + 1];
  }

  return [ans1, ans2];
}

async function main() {
  const lines = [];
  for await (const line of rl) {
    lines.push(line.trim());
  }

  let ptr = 0;
  while (ptr < lines.length) {
    const n = parseInt(lines[ptr++]);
    if (n === 0) break;

    const a = lines[ptr++].split(' ').map(Number);

    if (a.reduce((sum, num) => sum + num, 0) % 2 !== 0) {
      console.log("No");
      continue;
    }

    const even = [];
    const odd = [];
    for (let i = 0; i < n; i++) {
      if (a[i] % 2 === 0) {
        even.push([a[i], i]);
      } else {
        odd.push([a[i], i]);
      }
    }

    if (even.length > 0) {
      const res = [even[0], ...odd];
      const [ans1, ans2] = calc1(res);
      const B = Array(n).fill(-INF);
      const C = Array(n).fill(-INF);
      
      for (let i = 0; i < res.length; i++) {
        const idx = res[i][1];
        B[idx] = ans1[i];
        C[idx] = ans2[i];
      }

      for (let i = 0; i < n; i++) {
        if (B[i] === -INF) {
          B[i] = Math.floor(a[i] / 2);
          C[i] = Math.floor(a[i] / 2);
        }
      }

      console.log("Yes");
      console.log(B.join(' '));
      console.log(C.join(' '));
      continue;
    }

    const [ans1, ans2] = calc2(a);
    if (ans1[0] === -INF) {
      console.log("No");
    } else {
      console.log("Yes");
      console.log(ans1.join(' '));
      console.log(ans2.join(' '));
    }
  }
  rl.close();
}

main().catch(err => console.error(err));

Python solution:
# suzukaze_Aobayama

def calc1(res):
  #print(res)
  # odd many + even 1
  s=0
  for i in res:
    s+=i[0]
  s//=2
  m=len(res)
  #print(s)
  for i in range(1,m,2):
    s-=res[i][0]
  ans=[s]
  for i in range(m-1):
    ns=res[i][0]-s
    ans.append(ns)
    s=ns
  ans2=ans[1:]+ans[:1]
  return ans,ans2

def calc2(a):
  n=len(a)
  dp=[set() for i in range(n+1)]
  dp[0].add((0,0,0))
  for i in range(n):
    for sm,s1,s2 in dp[i]:
      if s1+1<=n//2:
        dp[i+1].add((sm+a[i],s1+1,s2))
      if s2+1<=n//2:
        dp[i+1].add((sm-a[i],s1,s2+1))
  ans1,ans2=[-inf]*n,[-inf]*n
  if (0,n//2,n//2) not in dp[n]:
    return ans1,ans2
  sm,s1,s2=0,n//2,n//2
  p0=[]
  p1=[]
  for i in range(n-1,-1,-1):
    if (sm-a[i],s1-1,s2) in dp[i]:
      p0.append(i)
      sm-=a[i]
      s1-=1
    else:
      p1.append(i)
      sm+=a[i]
      s2-=1
  p0=p0[::-1]
  p1=p1[::-1]
  
  perm=[]
  for i in range(n//2):
    perm.append(p0[i])
    perm.append(p1[i])
  
  A=[a[i] for i in perm]
  X=[0]
  s=0
  for i in A:
    ns=i-s
    X.append(ns)
    s=ns
  for i in range(n):
    ans1[perm[i]]=X[i+1]
    ans2[perm[(i+1)%n]]=X[i+1]
  return ans1,ans2


while True:
  n=int(input())
  if n==0:
    exit()
  a=list(map(int,input().split()))
  if sum(a)%2==1:
    print("No")
    continue
  even=[]
  odd=[]
  for i in range(n):
    if a[i]%2==0:
      even.append((a[i],i))
    else:
      odd.append((a[i],i))
  
  inf=1<<60
  if even:
    ans1,ans2=calc1([even[0]]+odd)
    B=[-inf]*n
    C=[-inf]*n
    res=[even[0]]+odd
    for i in range(len(res)):
      idx=res[i][1]
      B[idx]=ans1[i]
      C[idx]=ans2[i]
    for i in range(n):
      if B[i]==-inf:
        B[i]=a[i]//2
        C[i]=a[i]//2
    print("Yes")
    print(*B)
    print(*C)
    continue
  ans1,ans2=calc2(a)
  if ans1[0]==-inf:
    print("No")
  else:
    print("Yes")
    print(*ans1)
    print(*ans2)

Ruby solution:
def solve
  while true
    n = gets.to_i
    break if n == 0

    sums = gets.split.map(&:to_i)
    total = sums.sum
    if total % 2 != 0
      puts "No"
      next
    end

    even = []
    odd = []
    sums.each_with_index do |s, i|
      if s % 2 == 0
        even << [s, i]
      else
        odd << [s, i]
      end
    end

    if !even.empty?
      res = [even[0]] + odd
      ans1, ans2 = calc1(res, n)
      b = Array.new(n, -1)
      c = Array.new(n, -1)
      res.each_with_index do |(val, idx), i|
        b[idx] = ans1[i]
        c[idx] = ans2[i]
      end
      sums.each_with_index do |s, i|
        if b[i] == -1
          b[i] = s / 2
          c[i] = s / 2
        end
      end
      puts "Yes"
      puts b.join(' ')
      puts c.join(' ')
    else
      ans1, ans2 = calc2(sums)
      if ans1[0] == -1
        puts "No"
      else
        puts "Yes"
        puts ans1.join(' ')
        puts ans2.join(' ')
      end
    end
  end
end

def calc1(res, n)
  s = 0
  res.each { |val, _| s += val }
  s /= 2
  m = res.size
  (1...m).step(2) do |i|
    s -= res[i][0]
  end
  ans = [s]
  (0...m-1).each do |i|
    ns = res[i][0] - ans.last
    ans << ns
  end
  ans2 = ans[1..-1] + [ans[0]]
  [ans, ans2]
end

def calc2(a)
  n = a.size
  dp = Array.new(n + 1) { [] }
  dp[0] << [0, 0, 0]

  (0...n).each do |i|
    dp[i].each do |sm, s1, s2|
      if s1 + 1 <= n / 2
        dp[i + 1] << [sm + a[i], s1 + 1, s2]
      end
      if s2 + 1 <= n / 2
        dp[i + 1] << [sm - a[i], s1, s2 + 1]
      end
    end
    dp[i + 1].uniq!
  end

  ans1 = Array.new(n, -1)
  ans2 = Array.new(n, -1)
  target = [0, n / 2, n / 2]
  found = false
  dp[n].each do |state|
    if state == target
      found = true
      break
    end
  end
  unless found
    return [ans1, ans2]
  end

  sm = 0
  s1 = n / 2
  s2 = n / 2
  p0 = []
  p1 = []

  (n - 1).downto(0) do |i|
    if dp[i].include?([sm - a[i], s1 - 1, s2])
      p0 << i
      sm -= a[i]
      s1 -= 1
    else
      p1 << i
      sm += a[i]
      s2 -= 1
    end
  end

  p0 = p0.reverse
  p1 = p1.reverse

  perm = []
  (0...n / 2).each do |i|
    perm << p0[i]
    perm << p1[i]
  end

  x = [0]
  s = 0
  perm.each do |i|
    ns = a[i] - s
    x << ns
    s = ns
  end

  perm.each_with_index do |idx, i|
    ans1[idx] = x[i + 1]
    ans2[perm[(i + 1) % n]] = x[i + 1]
  end

  [ans1, ans2]
end

solve