#include <bits/stdc++.h>
using namespace std;
vector<vector<long long> > coprime(100001);
void prime_factorization() {
  for (long long i = 2; i <= 100001; i += 2) {
    coprime[i].push_back(2);
  }
  for (long long i = 3; i <= 100001; i += 3) {
    coprime[i].push_back(3);
  }
  for (long long i = 5; i <= 50000; i += 6) {
    if (coprime[i].size() == 0) {
      for (long long j = i; j <= 100000; j += i) {
        coprime[j].push_back(i);
      }
    }
    if (coprime[i + 2].size() == 0) {
      for (long long j = i + 2; j <= 100000; j += i + 2) {
        coprime[j].push_back(i + 2);
      }
    }
  }
}
bool isprime(long long n) {
  if (n < 2) return false;
  if (n == 2 || n == 3) return true;
  if (n % 2 == 0) return false;
  if (n % 3 == 0) return false;
  for (long long i = 5; i <= sqrt(n); i += 6) {
    if (n % i == 0 || n % (i + 2) == 0) return false;
  }
  return true;
}
void swap(long long &a, long long &b) {
  long long temp = a;
  a = b;
  b = temp;
}
long long bin_power(long long a, long long n) {
  if (a == 0) return 0;
  long long res = 1;
  while (n) {
    if (n % 2) {
      res = (res * a) % 1000000007;
      n--;
    } else {
      a = (a * a) % 1000000007;
      n /= 2;
    }
  }
  return res;
}
void p_factors(long long &n, map<long long, long long> &m) {
  if (n % 2 == 0) {
    long long c = 0;
    while (n % 2 == 0) {
      n /= 2;
      c++;
    }
    m[2] = c;
  }
  for (long long i = 3; i <= sqrt(n); i += 2) {
    if (n % i == 0) {
      long long c = 0;
      while (n % i == 0) {
        n /= i;
        c++;
      }
      m[i] = c;
    }
  }
  if (n != 1) m[n] = 1;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long extended_gcd(long long a, long long b, long long *x, long long *y) {
  if (a == 0) {
    *x = 0;
    *y = 1;
    return b;
  }
  long long x1, y1;
  long long g = extended_gcd(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return g;
}
void simple_sieve(long long n, vector<long long> &primes) {
  if (n < 2) return;
  if (n < 3) {
    primes.push_back(2);
    return;
  }
  vector<bool> mark(n + 1, true);
  mark[2] = true;
  mark[3] = true;
  primes.push_back(2);
  primes.push_back(3);
  for (long long i = 5; i * i < n; i += 6) {
    if (mark[i]) {
      for (long long j = i * i; j < n; j += i) mark[j] = false;
    }
    if (mark[i + 2] && (i + 2) < sqrt(n)) {
      for (long long j = (i + 2) * (i + 2); j < n; j += (i + 2))
        mark[j] = false;
    }
  }
  for (long long i = 5; i < n; i += 6) {
    if (mark[i]) primes.push_back(i);
    if (mark[i + 2] && (i + 2) < n) primes.push_back(i + 2);
  }
}
long long linear_sieve(long long n, vector<long long> &primes) {
  if (n < 2) return 0;
  if (n < 3) {
    primes.push_back(2);
    return 1;
  }
  vector<long long> mark(n + 1);
  for (long long i = 2; i <= n; i++) {
    if (mark[i] == 0) {
      primes.push_back(i);
      mark[i] = i;
    }
    for (long long j = 0;
         j < primes.size() && primes[j] <= mark[i] && i * primes[j] <= n; j++)
      mark[i * primes[j]] = primes[j];
  }
  return primes.size();
}
void segmented_sieve(long long n, vector<long long> &primes) {
  if (n < 2) return;
  long long limit = sqrt(n) + 1;
  simple_sieve(limit, primes);
  long long low = limit;
  long long high = 2 * limit;
  while (low < n) {
    if (high >= n) high = n + 1;
    vector<bool> mark(high - low + 2, true);
    for (long long i = 0; i < primes.size(); i++) {
      long long lolim = (low / primes[i]) * primes[i];
      if (lolim < low) lolim += primes[i];
      for (long long j = lolim; j < high; j += primes[i]) mark[j - low] = false;
    }
    for (long long j = low; j < high; j++) {
      if (mark[j - low]) primes.push_back(j);
    }
    low += limit;
    high += limit;
  }
}
void ranged_primes(long long low, long long high, vector<long long> &primes) {
  if (low < 2) low = 2;
  if (high < 2) return;
  long long lim = sqrt(high);
  vector<long long> pr;
  linear_sieve(lim, pr);
  if (pr.size() == 0) {
    if (high == 2) {
      primes.push_back(2);
      return;
    }
    if (high == 3) {
      if (low <= 2) {
        primes.push_back(2);
        primes.push_back(3);
        return;
      }
      primes.push_back(3);
      return;
    }
  }
  vector<bool> mark(high - low + 1, true);
  for (auto &i : pr) {
    long long j = i * i;
    if (j < low) {
      j = (low / i) * i;
      if (j < low) j += i;
    }
    while (j <= high) {
      mark[j - low] = false;
      j += i;
    }
  }
  for (long long i = low; i <= high; i++) {
    if (mark[i - low]) primes.push_back(i);
  }
}
long long totient(long long n) {
  long long res = n;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) {
        n /= i;
      }
      res -= res / i;
    }
  }
  if (n > 1) res -= res / n;
  return res;
}
void phi_1_to_n(long long n, vector<long long> &phi) {
  for (long long i = 0; i <= n; i++) {
    phi[i] = i;
  }
  for (long long i = 2; i <= n; i++) {
    if (phi[i] == i) {
      for (long long j = i; j <= n; j += i) {
        phi[j] -= phi[j] / i;
      }
    }
  }
}
long long factorial(long long n) {
  long long res = 1;
  for (long long i = 2; i <= n; i++) {
    res = (res * i) % 1000000007;
  }
  return res % 1000000007;
}
long long sumofint(long long n) {
  string s = to_string(n);
  long long sum = 0;
  for (long long i = 0; i < s.size(); i++) {
    int j = s[i];
    j -= 48;
    sum += j;
  }
  return sum;
}
long long modinverse(long long n) { return bin_power(n, 1000000007 - 2); }
long long ncr(long long n, long long r) {
  if (n < 0 || r > n || r < 0) return 0;
  if (n - r < r) r = n - r;
  vector<long long> c(n + 1);
  c[0] = 1;
  for (long long i = 1; i <= n; i++) {
    for (long long j = min(i, r); j > 0; j--) {
      c[j] = (c[j] + c[j - 1]) % 1000000007;
    }
  }
  return c[r] % 1000000007;
}
void dfsinto(long long v, vector<vector<long long> > &adj,
             vector<long long> &mark, stack<long long> &s) {
  mark[v] = 1;
  s.push(v);
  for (long long x : adj[v]) {
    if (!mark[x]) {
      dfsinto(x, adj, mark, s);
    }
  }
}
void dfs(vector<vector<long long> > &v, stack<long long> &s,
         vector<long long> &mark) {
  for (long long i = 0; i < 26; i++) {
    if (mark[i] || !v[i].size()) continue;
    dfsinto(i, v, mark, s);
  }
}
bool iscyclic(vector<vector<long long> > &g) {
  queue<long long> q;
  vector<long long> mark(26), p(26);
  for (long long i = 0; i < 26; i++) {
    if (mark[i] || !g[i].size()) continue;
    mark[i] = 1;
    q.push(i);
    p[i] = -1;
    while (!q.empty()) {
      long long f = q.front();
      q.pop();
      for (long long x : g[f]) {
        if (mark[x]) {
          if (x != p[f]) return true;
        } else {
          mark[x] = 1;
          q.push(x);
          p[x] = f;
        }
      }
    }
  }
  return false;
}
long long lcs(string &a, string &b, long long m, long long n, long long &l1,
              long long &l2) {
  vector<vector<long long> > L(n, vector<long long>(m));
  long long i, j, flag = 0;
  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
      if (a[i - 1] == b[j - 1]) {
        L[i][j] = L[i - 1][j - 1] + 1;
      } else
        L[i][j] = max(L[i - 1][j], L[i][j - 1]);
    }
  }
  return L[m][n];
}
bool issorted(vector<long long> &v, long long n) {
  for (long long i = 1; i < n; i++) {
    if (v[i] < v[i - 1]) return false;
  }
  return true;
}
string bin_string(long long n, long long l) {
  string s;
  for (long long i = l - 1; i >= 0; i--) {
    if (n % 2)
      s.push_back('1');
    else
      s.push_back('0');
    n /= 2;
  }
  reverse(s.begin(), s.end());
  return s;
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long tc = 1;
  while (tc--) {
    long long n, m, sa = 0, sb = 0, ans = 0;
    cin >> n;
    set<long long> s;
    for (long long i = 0; i < n; i++) {
      long long j;
      cin >> j;
      sa += j;
      s.insert(sa);
    }
    cin >> m;
    for (long long i = 0; i < m; i++) {
      long long j;
      cin >> j;
      sb += j;
      auto it = s.find(sb);
      if (it != s.end()) ans++;
    }
    if (sa == sb)
      cout << ans;
    else
      cout << "-1";
  }
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

Vasya has two arrays A and B of lengths n and m, respectively.

He can perform the following operation arbitrary number of times (possibly zero): he takes some consecutive subsegment of the array and replaces it with a single element, equal to the sum of all elements on this subsegment. For example, from the array [1, 10, 100, 1000, 10000] Vasya can obtain array [1, 1110, 10000], and from array [1, 2, 3] Vasya can obtain array [6].

Two arrays A and B are considered equal if and only if they have the same length and for each valid i A_i = B_i.

Vasya wants to perform some of these operations on array A, some on array B, in such a way that arrays A and B become equal. Moreover, the lengths of the resulting arrays should be maximal possible.

Help Vasya to determine the maximum length of the arrays that he can achieve or output that it is impossible to make arrays A and B equal.

Input

The first line contains a single integer n~(1 ≤ n ≤ 3 ⋅ 10^5) — the length of the first array.

The second line contains n integers a_1, a_2, ⋅⋅⋅, a_n~(1 ≤ a_i ≤ 10^9) — elements of the array A.

The third line contains a single integer m~(1 ≤ m ≤ 3 ⋅ 10^5) — the length of the second array.

The fourth line contains m integers b_1, b_2, ⋅⋅⋅, b_m~(1 ≤ b_i ≤ 10^9) - elements of the array B.

Output

Print a single integer — the maximum length of the resulting arrays after some operations were performed on arrays A and B in such a way that they became equal.

If there is no way to make array equal, print "-1".

Examples

Input

5
11 2 3 5 7
4
11 7 3 7


Output

3


Input

2
1 2
1
100


Output

-1


Input

3
1 2 3
3
1 2 3


Output

3

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
vector<vector<long long> > coprime(100001);
void prime_factorization() {
  for (long long i = 2; i <= 100001; i += 2) {
    coprime[i].push_back(2);
  }
  for (long long i = 3; i <= 100001; i += 3) {
    coprime[i].push_back(3);
  }
  for (long long i = 5; i <= 50000; i += 6) {
    if (coprime[i].size() == 0) {
      for (long long j = i; j <= 100000; j += i) {
        coprime[j].push_back(i);
      }
    }
    if (coprime[i + 2].size() == 0) {
      for (long long j = i + 2; j <= 100000; j += i + 2) {
        coprime[j].push_back(i + 2);
      }
    }
  }
}
bool isprime(long long n) {
  if (n < 2) return false;
  if (n == 2 || n == 3) return true;
  if (n % 2 == 0) return false;
  if (n % 3 == 0) return false;
  for (long long i = 5; i <= sqrt(n); i += 6) {
    if (n % i == 0 || n % (i + 2) == 0) return false;
  }
  return true;
}
void swap(long long &a, long long &b) {
  long long temp = a;
  a = b;
  b = temp;
}
long long bin_power(long long a, long long n) {
  if (a == 0) return 0;
  long long res = 1;
  while (n) {
    if (n % 2) {
      res = (res * a) % 1000000007;
      n--;
    } else {
      a = (a * a) % 1000000007;
      n /= 2;
    }
  }
  return res;
}
void p_factors(long long &n, map<long long, long long> &m) {
  if (n % 2 == 0) {
    long long c = 0;
    while (n % 2 == 0) {
      n /= 2;
      c++;
    }
    m[2] = c;
  }
  for (long long i = 3; i <= sqrt(n); i += 2) {
    if (n % i == 0) {
      long long c = 0;
      while (n % i == 0) {
        n /= i;
        c++;
      }
      m[i] = c;
    }
  }
  if (n != 1) m[n] = 1;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long extended_gcd(long long a, long long b, long long *x, long long *y) {
  if (a == 0) {
    *x = 0;
    *y = 1;
    return b;
  }
  long long x1, y1;
  long long g = extended_gcd(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return g;
}
void simple_sieve(long long n, vector<long long> &primes) {
  if (n < 2) return;
  if (n < 3) {
    primes.push_back(2);
    return;
  }
  vector<bool> mark(n + 1, true);
  mark[2] = true;
  mark[3] = true;
  primes.push_back(2);
  primes.push_back(3);
  for (long long i = 5; i * i < n; i += 6) {
    if (mark[i]) {
      for (long long j = i * i; j < n; j += i) mark[j] = false;
    }
    if (mark[i + 2] && (i + 2) < sqrt(n)) {
      for (long long j = (i + 2) * (i + 2); j < n; j += (i + 2))
        mark[j] = false;
    }
  }
  for (long long i = 5; i < n; i += 6) {
    if (mark[i]) primes.push_back(i);
    if (mark[i + 2] && (i + 2) < n) primes.push_back(i + 2);
  }
}
long long linear_sieve(long long n, vector<long long> &primes) {
  if (n < 2) return 0;
  if (n < 3) {
    primes.push_back(2);
    return 1;
  }
  vector<long long> mark(n + 1);
  for (long long i = 2; i <= n; i++) {
    if (mark[i] == 0) {
      primes.push_back(i);
      mark[i] = i;
    }
    for (long long j = 0;
         j < primes.size() && primes[j] <= mark[i] && i * primes[j] <= n; j++)
      mark[i * primes[j]] = primes[j];
  }
  return primes.size();
}
void segmented_sieve(long long n, vector<long long> &primes) {
  if (n < 2) return;
  long long limit = sqrt(n) + 1;
  simple_sieve(limit, primes);
  long long low = limit;
  long long high = 2 * limit;
  while (low < n) {
    if (high >= n) high = n + 1;
    vector<bool> mark(high - low + 2, true);
    for (long long i = 0; i < primes.size(); i++) {
      long long lolim = (low / primes[i]) * primes[i];
      if (lolim < low) lolim += primes[i];
      for (long long j = lolim; j < high; j += primes[i]) mark[j - low] = false;
    }
    for (long long j = low; j < high; j++) {
      if (mark[j - low]) primes.push_back(j);
    }
    low += limit;
    high += limit;
  }
}
void ranged_primes(long long low, long long high, vector<long long> &primes) {
  if (low < 2) low = 2;
  if (high < 2) return;
  long long lim = sqrt(high);
  vector<long long> pr;
  linear_sieve(lim, pr);
  if (pr.size() == 0) {
    if (high == 2) {
      primes.push_back(2);
      return;
    }
    if (high == 3) {
      if (low <= 2) {
        primes.push_back(2);
        primes.push_back(3);
        return;
      }
      primes.push_back(3);
      return;
    }
  }
  vector<bool> mark(high - low + 1, true);
  for (auto &i : pr) {
    long long j = i * i;
    if (j < low) {
      j = (low / i) * i;
      if (j < low) j += i;
    }
    while (j <= high) {
      mark[j - low] = false;
      j += i;
    }
  }
  for (long long i = low; i <= high; i++) {
    if (mark[i - low]) primes.push_back(i);
  }
}
long long totient(long long n) {
  long long res = n;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) {
        n /= i;
      }
      res -= res / i;
    }
  }
  if (n > 1) res -= res / n;
  return res;
}
void phi_1_to_n(long long n, vector<long long> &phi) {
  for (long long i = 0; i <= n; i++) {
    phi[i] = i;
  }
  for (long long i = 2; i <= n; i++) {
    if (phi[i] == i) {
      for (long long j = i; j <= n; j += i) {
        phi[j] -= phi[j] / i;
      }
    }
  }
}
long long factorial(long long n) {
  long long res = 1;
  for (long long i = 2; i <= n; i++) {
    res = (res * i) % 1000000007;
  }
  return res % 1000000007;
}
long long sumofint(long long n) {
  string s = to_string(n);
  long long sum = 0;
  for (long long i = 0; i < s.size(); i++) {
    int j = s[i];
    j -= 48;
    sum += j;
  }
  return sum;
}
long long modinverse(long long n) { return bin_power(n, 1000000007 - 2); }
long long ncr(long long n, long long r) {
  if (n < 0 || r > n || r < 0) return 0;
  if (n - r < r) r = n - r;
  vector<long long> c(n + 1);
  c[0] = 1;
  for (long long i = 1; i <= n; i++) {
    for (long long j = min(i, r); j > 0; j--) {
      c[j] = (c[j] + c[j - 1]) % 1000000007;
    }
  }
  return c[r] % 1000000007;
}
void dfsinto(long long v, vector<vector<long long> > &adj,
             vector<long long> &mark, stack<long long> &s) {
  mark[v] = 1;
  s.push(v);
  for (long long x : adj[v]) {
    if (!mark[x]) {
      dfsinto(x, adj, mark, s);
    }
  }
}
void dfs(vector<vector<long long> > &v, stack<long long> &s,
         vector<long long> &mark) {
  for (long long i = 0; i < 26; i++) {
    if (mark[i] || !v[i].size()) continue;
    dfsinto(i, v, mark, s);
  }
}
bool iscyclic(vector<vector<long long> > &g) {
  queue<long long> q;
  vector<long long> mark(26), p(26);
  for (long long i = 0; i < 26; i++) {
    if (mark[i] || !g[i].size()) continue;
    mark[i] = 1;
    q.push(i);
    p[i] = -1;
    while (!q.empty()) {
      long long f = q.front();
      q.pop();
      for (long long x : g[f]) {
        if (mark[x]) {
          if (x != p[f]) return true;
        } else {
          mark[x] = 1;
          q.push(x);
          p[x] = f;
        }
      }
    }
  }
  return false;
}
long long lcs(string &a, string &b, long long m, long long n, long long &l1,
              long long &l2) {
  vector<vector<long long> > L(n, vector<long long>(m));
  long long i, j, flag = 0;
  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
      if (a[i - 1] == b[j - 1]) {
        L[i][j] = L[i - 1][j - 1] + 1;
      } else
        L[i][j] = max(L[i - 1][j], L[i][j - 1]);
    }
  }
  return L[m][n];
}
bool issorted(vector<long long> &v, long long n) {
  for (long long i = 1; i < n; i++) {
    if (v[i] < v[i - 1]) return false;
  }
  return true;
}
string bin_string(long long n, long long l) {
  string s;
  for (long long i = l - 1; i >= 0; i--) {
    if (n % 2)
      s.push_back('1');
    else
      s.push_back('0');
    n /= 2;
  }
  reverse(s.begin(), s.end());
  return s;
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long tc = 1;
  while (tc--) {
    long long n, m, sa = 0, sb = 0, ans = 0;
    cin >> n;
    set<long long> s;
    for (long long i = 0; i < n; i++) {
      long long j;
      cin >> j;
      sa += j;
      s.insert(sa);
    }
    cin >> m;
    for (long long i = 0; i < m; i++) {
      long long j;
      cin >> j;
      sb += j;
      auto it = s.find(sb);
      if (it != s.end()) ans++;
    }
    if (sa == sb)
      cout << ans;
    else
      cout << "-1";
  }
  return 0;
}

```