#include <bits/stdc++.h>
using namespace std;
int inf;
const double eps = 1e-8;
const double pi = acos(-1.0);
template <class T, class T2>
int chkmin(T &a, T2 b) {
  return a > b ? a = b, 1 : 0;
}
template <class T, class T2>
int chkmax(T &a, T2 b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T, class T2>
T mmin(T a, T2 b) {
  return a < b ? a : b;
}
template <class T, class T2>
T mmax(T a, T2 b) {
  return a > b ? a : b;
}
template <class T>
T aabs(T a) {
  return a < 0 ? -a : a;
}
template <class T>
int dcmp(T a, T b) {
  return a > b;
}
template <int *a>
int cmp_a(int first, int second) {
  return a[first] < a[second];
}
struct __INIT__ {
  __INIT__() { memset(&inf, 0x3f, sizeof(inf)); }
} __INIT___;
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
int f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char first) {
  *oS++ = first;
  if (oS == oT) flush();
}
template <typename A>
inline bool read(A &first) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (first = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    first = first * 10 + (c & 15);
  first *= f;
  return 1;
}
inline bool read(char &first) {
  while ((first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                               (iS == iT ? EOF : *iS++))
                            : *iS++)) == ' ' ||
         first == '\n' || first == '\r')
    ;
  return first != EOF;
}
inline bool read(char *first) {
  while ((*first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                                (iS == iT ? EOF : *iS++))
                             : *iS++)) == '\n' ||
         *first == ' ' || *first == '\r')
    ;
  if (*first == EOF) return 0;
  while (!(*first == '\n' || *first == ' ' || *first == '\r' || *first == EOF))
    *(++first) = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                           : *iS++);
  *first = 0;
  return 1;
}
template <typename A, typename... B>
inline bool read(A &first, B &...second) {
  return read(first) && read(second...);
}
template <typename A>
inline bool write(A first) {
  if (!first) putc('0');
  if (first < 0) putc('-'), first = -first;
  while (first) qu[++qr] = first % 10 + '0', first /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(char first) {
  putc(first);
  return 0;
}
inline bool write(const char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
inline bool write(char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
template <typename A, typename... B>
inline bool write(A first, B... second) {
  return write(first) || write(second...);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::putc;
using io ::read;
using io ::write;
int a[100005], b[100005], c[100005], w[100005], las[100005];
int out[100005];
int t;
int mx[100005], pmx[100005], f[100005], xlas[100005];
int fm[100005];
void add(int first, int second) {
  for (; first <= t; first += first & -first) chkmax(mx[first], second);
}
int query(int first) {
  int second = 0;
  for (; first; first ^= first & -first) chkmax(second, mx[first]);
  return second;
}
signed main() {
  int n, m;
  read(n);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
    out[i] = a[i];
  }
  read(m);
  for (int i = 1; i <= m; ++i) {
    read(w[i]);
  }
  sort(w + 1, w + m + 1);
  t = 0;
  for (int i = 1; i <= m; ++i) {
    if (b[t] != w[i]) b[++t] = w[i];
    ++c[t];
  }
  m = t;
  int cnt = 0;
  for (int i = 1; i <= n; ++i)
    if (~a[i]) {
      w[++cnt] = a[i];
    }
  sort(w + 1, w + cnt + 1);
  t = unique(w + 1, w + cnt + 1) - w - 1;
  w[++t] = inf;
  for (int i = 1, j = 0; i <= t; ++i) {
    while (j < m && b[j + 1] < w[i]) ++j;
    las[i] = j;
  }
  for (int i = 1; i <= n; ++i)
    if (~a[i]) a[i] = lower_bound(w + 1, w + t + 1, a[i]) - w;
  a[++n] = t;
  for (int i = 1; i <= n; ++i) {
    if (~a[i]) {
      if (chkmax(f[i], query(a[i] - 1) + 1)) xlas[i] = 0;
      if (chkmax(pmx[a[i]], f[i])) add(a[i], f[i]);
    } else {
      for (int j = 1, k = 1, mx = 0; j <= m; ++j) {
        while (k <= t && w[k] < b[j]) {
          chkmax(mx, pmx[k]);
          ++k;
        }
        fm[j] = mx;
      }
      for (int j = i + 1, w = 0; j <= n; ++j)
        if (~a[j]) {
          if (las[a[j]] > w && chkmax(f[j], fm[las[a[j]] - w] + w + 2))
            xlas[j] = i;
        } else
          ++w;
    }
  }
  int at = n;
  while (f[at] > 1) {
    if (!xlas[at]) {
      int i = at - 1;
      while (i) {
        if (~a[i] && a[i] < a[at] && f[i] + 1 == f[at]) {
          at = i;
          break;
        }
        --i;
      }
    } else {
      int xf = f[at];
      int s = las[a[at]], i = at;
      while (i >= xlas[at]) {
        if (!~a[i]) {
          out[i] = b[s];
          --c[s];
          --s;
          --xf;
        }
        --i;
      }
      while (i) {
        if (~a[i] && a[i] < b[s + 1] && f[i] + 1 == xf) {
          at = i;
          break;
        }
        --i;
      }
      if (!i) at = 0;
    }
  }
  --n;
  for (int i = 1, j = 1; i <= n; ++i)
    if (!~out[i]) {
      while (!c[j]) ++j;
      --c[j];
      out[i] = b[j];
    }
  for (int i = 1; i <= n; ++i) write(out[i], i == n ? '\n' : ' ');
  return 0;
}

### Prompt

Generate a Cpp solution to the following problem:

Note that the memory limit in this problem is less than usual.

Let's consider an array consisting of positive integers, some positions of which contain gaps.

We have a collection of numbers that can be used to fill the gaps. Each number from the given collection can be used at most once.

Your task is to determine such way of filling gaps that the longest increasing subsequence in the formed array has a maximum size.

Input

The first line contains a single integer n — the length of the array (1 ≤ n ≤ 105).

The second line contains n space-separated integers — the elements of the sequence. A gap is marked as "-1". The elements that are not gaps are positive integers not exceeding 109. It is guaranteed that the sequence contains 0 ≤ k ≤ 1000 gaps.

The third line contains a single positive integer m — the number of elements to fill the gaps (k ≤ m ≤ 105).

The fourth line contains m positive integers — the numbers to fill gaps. Each number is a positive integer not exceeding 109. Some numbers may be equal. 

Output

Print n space-separated numbers in a single line — the resulting sequence. If there are multiple possible answers, print any of them.

Examples

Input

3
1 2 3
1
10


Output

1 2 3 


Input

3
1 -1 3
3
1 2 3


Output

1 2 3 


Input

2
-1 2
2
2 4


Output

2 2 


Input

3
-1 -1 -1
5
1 1 1 1 2


Output

1 1 2 


Input

4
-1 -1 -1 2
4
1 1 2 2


Output

1 2 1 2 

Note

In the first sample there are no gaps, so the correct answer is the initial sequence.

In the second sample there is only one way to get an increasing subsequence of length 3.

In the third sample answer "4 2" would also be correct. Note that only strictly increasing subsequences are considered.

In the fifth sample the answer "1 1 1 2" is not considered correct, as number 1 can be used in replacing only two times.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int inf;
const double eps = 1e-8;
const double pi = acos(-1.0);
template <class T, class T2>
int chkmin(T &a, T2 b) {
  return a > b ? a = b, 1 : 0;
}
template <class T, class T2>
int chkmax(T &a, T2 b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T, class T2>
T mmin(T a, T2 b) {
  return a < b ? a : b;
}
template <class T, class T2>
T mmax(T a, T2 b) {
  return a > b ? a : b;
}
template <class T>
T aabs(T a) {
  return a < 0 ? -a : a;
}
template <class T>
int dcmp(T a, T b) {
  return a > b;
}
template <int *a>
int cmp_a(int first, int second) {
  return a[first] < a[second];
}
struct __INIT__ {
  __INIT__() { memset(&inf, 0x3f, sizeof(inf)); }
} __INIT___;
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
int f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char first) {
  *oS++ = first;
  if (oS == oT) flush();
}
template <typename A>
inline bool read(A &first) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (first = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    first = first * 10 + (c & 15);
  first *= f;
  return 1;
}
inline bool read(char &first) {
  while ((first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                               (iS == iT ? EOF : *iS++))
                            : *iS++)) == ' ' ||
         first == '\n' || first == '\r')
    ;
  return first != EOF;
}
inline bool read(char *first) {
  while ((*first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                                (iS == iT ? EOF : *iS++))
                             : *iS++)) == '\n' ||
         *first == ' ' || *first == '\r')
    ;
  if (*first == EOF) return 0;
  while (!(*first == '\n' || *first == ' ' || *first == '\r' || *first == EOF))
    *(++first) = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                           : *iS++);
  *first = 0;
  return 1;
}
template <typename A, typename... B>
inline bool read(A &first, B &...second) {
  return read(first) && read(second...);
}
template <typename A>
inline bool write(A first) {
  if (!first) putc('0');
  if (first < 0) putc('-'), first = -first;
  while (first) qu[++qr] = first % 10 + '0', first /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(char first) {
  putc(first);
  return 0;
}
inline bool write(const char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
inline bool write(char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
template <typename A, typename... B>
inline bool write(A first, B... second) {
  return write(first) || write(second...);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::putc;
using io ::read;
using io ::write;
int a[100005], b[100005], c[100005], w[100005], las[100005];
int out[100005];
int t;
int mx[100005], pmx[100005], f[100005], xlas[100005];
int fm[100005];
void add(int first, int second) {
  for (; first <= t; first += first & -first) chkmax(mx[first], second);
}
int query(int first) {
  int second = 0;
  for (; first; first ^= first & -first) chkmax(second, mx[first]);
  return second;
}
signed main() {
  int n, m;
  read(n);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
    out[i] = a[i];
  }
  read(m);
  for (int i = 1; i <= m; ++i) {
    read(w[i]);
  }
  sort(w + 1, w + m + 1);
  t = 0;
  for (int i = 1; i <= m; ++i) {
    if (b[t] != w[i]) b[++t] = w[i];
    ++c[t];
  }
  m = t;
  int cnt = 0;
  for (int i = 1; i <= n; ++i)
    if (~a[i]) {
      w[++cnt] = a[i];
    }
  sort(w + 1, w + cnt + 1);
  t = unique(w + 1, w + cnt + 1) - w - 1;
  w[++t] = inf;
  for (int i = 1, j = 0; i <= t; ++i) {
    while (j < m && b[j + 1] < w[i]) ++j;
    las[i] = j;
  }
  for (int i = 1; i <= n; ++i)
    if (~a[i]) a[i] = lower_bound(w + 1, w + t + 1, a[i]) - w;
  a[++n] = t;
  for (int i = 1; i <= n; ++i) {
    if (~a[i]) {
      if (chkmax(f[i], query(a[i] - 1) + 1)) xlas[i] = 0;
      if (chkmax(pmx[a[i]], f[i])) add(a[i], f[i]);
    } else {
      for (int j = 1, k = 1, mx = 0; j <= m; ++j) {
        while (k <= t && w[k] < b[j]) {
          chkmax(mx, pmx[k]);
          ++k;
        }
        fm[j] = mx;
      }
      for (int j = i + 1, w = 0; j <= n; ++j)
        if (~a[j]) {
          if (las[a[j]] > w && chkmax(f[j], fm[las[a[j]] - w] + w + 2))
            xlas[j] = i;
        } else
          ++w;
    }
  }
  int at = n;
  while (f[at] > 1) {
    if (!xlas[at]) {
      int i = at - 1;
      while (i) {
        if (~a[i] && a[i] < a[at] && f[i] + 1 == f[at]) {
          at = i;
          break;
        }
        --i;
      }
    } else {
      int xf = f[at];
      int s = las[a[at]], i = at;
      while (i >= xlas[at]) {
        if (!~a[i]) {
          out[i] = b[s];
          --c[s];
          --s;
          --xf;
        }
        --i;
      }
      while (i) {
        if (~a[i] && a[i] < b[s + 1] && f[i] + 1 == xf) {
          at = i;
          break;
        }
        --i;
      }
      if (!i) at = 0;
    }
  }
  --n;
  for (int i = 1, j = 1; i <= n; ++i)
    if (!~out[i]) {
      while (!c[j]) ++j;
      --c[j];
      out[i] = b[j];
    }
  for (int i = 1; i <= n; ++i) write(out[i], i == n ? '\n' : ' ');
  return 0;
}

```