Don't you tell me what you think that I can be

If you say that Arkady is a bit old-fashioned playing checkers, you won't be right. There is also a modern computer game Arkady and his friends are keen on. We won't discuss its rules, the only feature important to this problem is that each player has to pick a distinct hero in the beginning of the game.

There are 2 teams each having n players and 2n heroes to distribute between the teams. The teams take turns picking heroes: at first, the first team chooses a hero in its team, after that the second team chooses a hero and so on. Note that after a hero is chosen it becomes unavailable to both teams.

The friends estimate the power of the i-th of the heroes as p_i. Each team wants to maximize the total power of its heroes. However, there is one exception: there are m pairs of heroes that are especially strong against each other, so when any team chooses a hero from such a pair, the other team must choose the other one on its turn. Each hero is in at most one such pair.

This is an interactive problem. You are to write a program that will optimally choose the heroes for one team, while the jury's program will play for the other team. Note that the jury's program may behave inefficiently, in this case you have to take the opportunity and still maximize the total power of your team. Formally, if you ever have chance to reach the total power of q or greater regardless of jury's program choices, you must get q or greater to pass a test.

Input

The first line contains two integers n and m (1 ≤ n ≤ 10^3, 0 ≤ m ≤ n) — the number of players in one team and the number of special pairs of heroes.

The second line contains 2n integers p_1, p_2, …, p_{2n} (1 ≤ p_i ≤ 10^3) — the powers of the heroes.

Each of the next m lines contains two integer a and b (1 ≤ a, b ≤ 2n, a ≠ b) — a pair of heroes that are especially strong against each other. It is guaranteed that each hero appears at most once in this list.

The next line contains a single integer t (1 ≤ t ≤ 2) — the team you are to play for. If t = 1, the first turn is yours, otherwise you have the second turn.

Hacks

In order to hack, use the format described above with one additional line. In this line output 2n distinct integers from 1 to 2n — the priority order for the jury's team. The jury's team will on each turn select the first possible hero from this list. Here possible means that it is not yet taken and does not contradict the rules about special pair of heroes.

Interaction

When it is your turn, print a single integer x (1 ≤ x ≤ 2n) — the index of the hero chosen by you. Note that you can't choose a hero previously chosen by either you of the other player, and you must follow the rules about special pairs of heroes.

When it is the other team's turn, read a line containing a single integer x (1 ≤ x ≤ 2n) — the index of the hero chosen by the other team. It is guaranteed that this index is not chosen before and that the other team also follows the rules about special pairs of heroes.

After the last turn you should terminate without printing anything.

After printing your choice do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



Jury's answer -1 instead of a valid choice means that you made an invalid turn. Exit immediately after receiving -1 and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Examples

Input


3 1
1 2 3 4 5 6
2 6
1

2

4

1


Output






6

5

3


Input


3 1
1 2 3 4 5 6
1 5
2
6

1

3


Output







5

4

2

Note

In the first example the first turn is yours. In example, you choose 6, the other team is forced to reply with 2. You choose 5, the other team chooses 4. Finally, you choose 3 and the other team choose 1.

In the second example you have the second turn. The other team chooses 6, you choose 5, forcing the other team to choose 1. Now you choose 4, the other team chooses 3 and you choose 2.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pill = pair<int, ll>;
using plli = pair<ll, int>;
using pdd = pair<double, double>;
using pld = pair<ld, ld>;
constexpr const char nl = '\n', sp = ' ';
constexpr const int INT_INF = 0x3f3f3f3f;
constexpr const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
constexpr const double D_INF = numeric_limits<double>::infinity();
constexpr const ld LD_INF = numeric_limits<ld>::infinity();
template <class T>
constexpr const T& _min(const T& x, const T& y) {
  return x < y ? x : y;
}
template <class T>
constexpr const T& _max(const T& x, const T& y) {
  return x < y ? y : x;
}
template <class T, class... Ts>
constexpr const T& _min(const T& x, const Ts&... xs) {
  return _min(x, _min(xs...));
}
template <class T, class... Ts>
constexpr const T& _max(const T& x, const Ts&... xs) {
  return _max(x, _max(xs...));
}
template <class T, class... Ts>
void MIN(T& x, const Ts&... xs) {
  x = _min(x, xs...);
}
template <class T, class... Ts>
void MAX(T& x, const Ts&... xs) {
  x = _max(x, xs...);
}
template <class T>
constexpr const T& _clamp(const T& v, const T& lo, const T& hi) {
  return v < lo ? lo : hi < v ? hi : v;
}
template <class T>
void CLAMP(T& v, const T& lo, const T& hi) {
  v = _clamp(v, lo, hi);
}
template <class T, class... Args>
unique_ptr<T> _make_unique(Args&&... args) {
  return unique_ptr<T>(new T(forward<Args>(args)...));
}
template <class T, class... Args>
shared_ptr<T> _make_shared(Args&&... args) {
  return shared_ptr<T>(new T(forward<Args>(args)...));
}
template <class... Ts>
using uset = unordered_set<Ts...>;
template <class... Ts>
using umap = unordered_map<Ts...>;
template <class... Ts>
using pq = priority_queue<Ts...>;
template <class T>
using minpq = pq<T, vector<T>, greater<T>>;
template <class T>
using maxpq = pq<T, vector<T>, less<T>>;
template <class T1, class T2, class H1 = hash<T1>, class H2 = hash<T2>>
struct pair_hash {
  size_t operator()(const pair<T1, T2>& p) const {
    return 31 * H1{}(p.first) + H2{}(p.second);
  }
};
template <class T>
struct is_iterator {
  template <class U, typename enable_if<!is_convertible<U, const char*>::value,
                                        int>::type = 0>
  constexpr static auto has_indirection(int)
      -> decltype(*declval<U>(), bool()) {
    return true;
  }
  template <class>
  constexpr static bool has_indirection(long) {
    return false;
  }
  constexpr static bool value = has_indirection<T>(0);
};
seed_seq seq{(uint64_t)chrono::duration_cast<chrono::nanoseconds>(
                 chrono::high_resolution_clock::now().time_since_epoch())
                 .count(),
             (uint64_t)__builtin_ia32_rdtsc(),
             (uint64_t)(uintptr_t)_make_unique<char>().get()};
mt19937 rng(seq);
mt19937_64 rng64(seq);
constexpr const int _bufferSize = 4096, _maxNumLength = 128;
char _inputBuffer[_bufferSize + 1],
    *_inputPtr = _inputBuffer, _outputBuffer[_bufferSize], _c, _sign,
    *_tempInputBuf = nullptr, _numBuf[_maxNumLength],
    _tempOutputBuf[_maxNumLength], _fill = ' ';
FILE *_input = stdin, *_output = stdout, *_error = stderr;
const char* _delimiter = " ";
int _cur, _outputPtr = 0, _numPtr = 0, _precision = 6, _width = 0,
          _tempOutputPtr = 0, _cnt;
ull _precisionBase = 1000000;
void read(int& x) {
  do {
    do {
      (x) = (getchar());
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign) (x) = (getchar());
    for ((x) -= '0'; (_c = (getchar())) >= '0'; (x) = (x)*10 + _c - '0')
      ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(uint& x) {
  do {
    do {
      (x) = (getchar());
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign) (x) = (getchar());
    for ((x) -= '0'; (_c = (getchar())) >= '0'; (x) = (x)*10 + _c - '0')
      ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(ll& x) {
  do {
    do {
      (x) = (getchar());
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign) (x) = (getchar());
    for ((x) -= '0'; (_c = (getchar())) >= '0'; (x) = (x)*10 + _c - '0')
      ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(ull& x) {
  do {
    do {
      (x) = (getchar());
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign) (x) = (getchar());
    for ((x) -= '0'; (_c = (getchar())) >= '0'; (x) = (x)*10 + _c - '0')
      ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(double& x) {
  do {
    do {
      (x) = (getchar());
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign) (x) = (getchar());
    for ((x) -= '0'; (_c = (getchar())) >= '0'; (x) = (x)*10 + _c - '0')
      ;
    if (_c == '.')
      for (double _div = 1.0; (_c = (getchar())) >= '0';
           (x) += (_c - '0') / (_div *= 10))
        ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(ld& x) {
  do {
    do {
      (x) = (getchar());
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign) (x) = (getchar());
    for ((x) -= '0'; (_c = (getchar())) >= '0'; (x) = (x)*10 + _c - '0')
      ;
    if (_c == '.')
      for (ld _div = 1.0; (_c = (getchar())) >= '0';
           (x) += (_c - '0') / (_div *= 10))
        ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(char& x) {
  do {
    do {
      (x) = (getchar());
    } while ((x) <= ' ');
  } while (0);
}
void read(char* x) {
  do {
    _cur = 0;
    do {
      _c = (getchar());
    } while (_c <= ' ');
    do {
      (x)[_cur++] = _c;
    } while ((_c = (getchar())) > ' ');
    (x)[_cur] = '\0';
  } while (0);
}
void read(string& x) {
  do {
    if (!_tempInputBuf) assert(0);
    do {
      _cur = 0;
      do {
        _c = (getchar());
      } while (_c <= ' ');
      do {
        (_tempInputBuf)[_cur++] = _c;
      } while ((_c = (getchar())) > ' ');
      (_tempInputBuf)[_cur] = '\0';
    } while (0);
    (x) = string(_tempInputBuf, _cur);
  } while (0);
}
void readln(char* x) {
  do {
    _cur = 0;
    do {
      _c = (getchar());
    } while (_c <= ' ');
    do {
      (x)[_cur++] = _c;
    } while ((_c = (getchar())) >= ' ');
    (x)[_cur] = '\0';
  } while (0);
}
void readln(string& x) {
  do {
    if (!_tempInputBuf) assert(0);
    do {
      _cur = 0;
      do {
        _c = (getchar());
      } while (_c <= ' ');
      do {
        (_tempInputBuf)[_cur++] = _c;
      } while ((_c = (getchar())) >= ' ');
      (_tempInputBuf)[_cur] = '\0';
    } while (0);
    (x) = string(_tempInputBuf, _cur);
  } while (0);
}
template <class T1, class T2>
void read(pair<T1, T2>& x) {
  read(x.first);
  read(x.second);
}
template <class T>
void read(complex<T>& x) {
  T _re, _im;
  read(_re);
  read(_im);
  x.real(_re);
  x.imag(_im);
}
template <class T>
void read(T& x);
template <class T, class... Ts>
void read(T& x, Ts&&... xs);
template <class It>
typename enable_if<is_iterator<It>::value>::type read(It st, It en) {
  for (It _i = st; _i != en; _i++) read(*_i);
}
template <class It, class... Ts>
typename enable_if<is_iterator<It>::value>::type read(It st, It en,
                                                      Ts&&... xs) {
  read(st, en);
  read(forward<Ts>(xs)...);
}
template <class T>
void read(T& x) {
  for (auto&& _i : x) read(_i);
}
template <class T, class... Ts>
void read(T& x, Ts&&... xs) {
  read(x);
  read(forward<Ts>(xs)...);
}
bool hasNext() {
  while ((*_inputPtr || !feof(_input)) &&
         (*_inputPtr ? *_inputPtr
                     : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                                           _bufferSize, _input)] = '\0',
                        *_inputPtr)) <= ' ')
    (getchar());
  return (*_inputPtr || !feof(_input));
}
void setInput(FILE* file) {
  *_inputPtr = '\0';
  _input = file;
}
void setInput(const char* second) {
  *_inputPtr = '\0';
  _input = fopen(second, "r");
}
void setInput(const string& second) {
  *_inputPtr = '\0';
  _input = fopen(second.c_str(), "r");
}
void writeDelimiter() {
  for (const char* _p = _delimiter; *_p;
       (_outputBuffer[_outputPtr == _bufferSize
                          ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                             _outputPtr = 0)
                          : _outputPtr] = (*_p++),
                            _outputPtr++))
    ;
}
void write(const bool& x) {
  do {
    if (x)
      (_tempOutputBuf[_tempOutputPtr++] = ('1'));
    else
      (_tempOutputBuf[_tempOutputPtr++] = ('0'));
    int _tempLen = _tempOutputPtr;
    for (int _i = 0; _i < (_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == _bufferSize
                            ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(const int& x) {
  do {
    if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      _cnt = 0;
      for (uint _y = (-(x)); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < 1; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
    } else {
      _cnt = 0;
      for (uint _y = (x); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < 1; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
    }
    int _tempLen = _tempOutputPtr;
    for (int _i = 0; _i < (_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == _bufferSize
                            ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(const uint& x) {
  do {
    if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      _cnt = 0;
      for (uint _y = (-(x)); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < 1; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
    } else {
      _cnt = 0;
      for (uint _y = (x); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < 1; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
    }
    int _tempLen = _tempOutputPtr;
    for (int _i = 0; _i < (_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == _bufferSize
                            ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(const ll& x) {
  do {
    if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      _cnt = 0;
      for (ull _y = (-(x)); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < 1; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
    } else {
      _cnt = 0;
      for (ull _y = (x); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < 1; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
    }
    int _tempLen = _tempOutputPtr;
    for (int _i = 0; _i < (_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == _bufferSize
                            ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(const ull& x) {
  do {
    if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      _cnt = 0;
      for (ull _y = (-(x)); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < 1; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
    } else {
      _cnt = 0;
      for (ull _y = (x); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < 1; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
    }
    int _tempLen = _tempOutputPtr;
    for (int _i = 0; _i < (_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == _bufferSize
                            ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(const double& x) {
  do {
    if (std::isnan(x)) {
      do {
        int _slen = strlen("NaN");
        for (int _i = 0; _i < (_width - _slen); _i++)
          (_outputBuffer[_outputPtr == _bufferSize
                             ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
        for (const char* _p = ("NaN"); *_p;
             (_outputBuffer[_outputPtr == _bufferSize
                                ? (fwrite(_outputBuffer, 1, _outputPtr,
                                          _output),
                                   _outputPtr = 0)
                                : _outputPtr] = (*_p++),
                                  _outputPtr++))
          ;
        for (int _i = 0; _i < (-_width - _slen); _i++)
          (_outputBuffer[_outputPtr == _bufferSize
                             ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
      } while (0);
    } else if (std::isinf(x)) {
      do {
        int _slen = strlen("Inf");
        for (int _i = 0; _i < (_width - _slen); _i++)
          (_outputBuffer[_outputPtr == _bufferSize
                             ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
        for (const char* _p = ("Inf"); *_p;
             (_outputBuffer[_outputPtr == _bufferSize
                                ? (fwrite(_outputBuffer, 1, _outputPtr,
                                          _output),
                                   _outputPtr = 0)
                                : _outputPtr] = (*_p++),
                                  _outputPtr++))
          ;
        for (int _i = 0; _i < (-_width - _slen); _i++)
          (_outputBuffer[_outputPtr == _bufferSize
                             ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
      } while (0);
    } else if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      ull _I = (ull)(-(x));
      ull _F = ((-(x)) - _I) * _precisionBase + (double)(0.5);
      if (_F >= _precisionBase) {
        _I++;
        _F = 0;
      }
      _cnt = 0;
      for (ull _y = (_I); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < 1; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
      (_tempOutputBuf[_tempOutputPtr++] = ('.'));
      _cnt = 0;
      for (ull _y = (_F); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < _precision; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
    } else {
      ull _I = (ull)(x);
      ull _F = ((x)-_I) * _precisionBase + (double)(0.5);
      if (_F >= _precisionBase) {
        _I++;
        _F = 0;
      }
      _cnt = 0;
      for (ull _y = (_I); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < 1; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
      (_tempOutputBuf[_tempOutputPtr++] = ('.'));
      _cnt = 0;
      for (ull _y = (_F); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < _precision; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
    }
    int _tempLen = _tempOutputPtr;
    for (int _i = 0; _i < (_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == _bufferSize
                            ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(const ld& x) {
  do {
    if (std::isnan(x)) {
      do {
        int _slen = strlen("NaN");
        for (int _i = 0; _i < (_width - _slen); _i++)
          (_outputBuffer[_outputPtr == _bufferSize
                             ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
        for (const char* _p = ("NaN"); *_p;
             (_outputBuffer[_outputPtr == _bufferSize
                                ? (fwrite(_outputBuffer, 1, _outputPtr,
                                          _output),
                                   _outputPtr = 0)
                                : _outputPtr] = (*_p++),
                                  _outputPtr++))
          ;
        for (int _i = 0; _i < (-_width - _slen); _i++)
          (_outputBuffer[_outputPtr == _bufferSize
                             ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
      } while (0);
    } else if (std::isinf(x)) {
      do {
        int _slen = strlen("Inf");
        for (int _i = 0; _i < (_width - _slen); _i++)
          (_outputBuffer[_outputPtr == _bufferSize
                             ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
        for (const char* _p = ("Inf"); *_p;
             (_outputBuffer[_outputPtr == _bufferSize
                                ? (fwrite(_outputBuffer, 1, _outputPtr,
                                          _output),
                                   _outputPtr = 0)
                                : _outputPtr] = (*_p++),
                                  _outputPtr++))
          ;
        for (int _i = 0; _i < (-_width - _slen); _i++)
          (_outputBuffer[_outputPtr == _bufferSize
                             ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
      } while (0);
    } else if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      ull _I = (ull)(-(x));
      ull _F = ((-(x)) - _I) * _precisionBase + (ld)(0.5);
      if (_F >= _precisionBase) {
        _I++;
        _F = 0;
      }
      _cnt = 0;
      for (ull _y = (_I); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < 1; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
      (_tempOutputBuf[_tempOutputPtr++] = ('.'));
      _cnt = 0;
      for (ull _y = (_F); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < _precision; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
    } else {
      ull _I = (ull)(x);
      ull _F = ((x)-_I) * _precisionBase + (ld)(0.5);
      if (_F >= _precisionBase) {
        _I++;
        _F = 0;
      }
      _cnt = 0;
      for (ull _y = (_I); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < 1; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
      (_tempOutputBuf[_tempOutputPtr++] = ('.'));
      _cnt = 0;
      for (ull _y = (_F); _y; _y /= 10, _cnt++)
        _numBuf[_numPtr++] = '0' + _y % 10;
      for (; _cnt < _precision; _cnt++) _numBuf[_numPtr++] = '0';
      for (; _numPtr; (_tempOutputBuf[_tempOutputPtr++] = (_numBuf[--_numPtr])))
        ;
      ;
    }
    int _tempLen = _tempOutputPtr;
    for (int _i = 0; _i < (_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == _bufferSize
                            ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(const char& x) {
  do {
    (_tempOutputBuf[_tempOutputPtr++] = (x));
    int _tempLen = _tempOutputPtr;
    for (int _i = 0; _i < (_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == _bufferSize
                            ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(const char* x) {
  do {
    int _slen = strlen(x);
    for (int _i = 0; _i < (_width - _slen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (const char* _p = (x); *_p;
         (_outputBuffer[_outputPtr == _bufferSize
                            ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                               _outputPtr = 0)
                            : _outputPtr] = (*_p++),
                              _outputPtr++))
      ;
    for (int _i = 0; _i < (-_width - _slen); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(const string& x) {
  do {
    for (int _i = 0; _i < (_width - int((x).length())); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < int((x).length());
         (_outputBuffer[_outputPtr == _bufferSize
                            ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                               _outputPtr = 0)
                            : _outputPtr] = (x[_i++]),
                              _outputPtr++))
      ;
    for (int _i = 0; _i < (-_width - int((x).length())); _i++)
      (_outputBuffer[_outputPtr == _bufferSize
                         ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
template <class T1, class T2>
void write(const pair<T1, T2>& x) {
  write(x.first);
  writeDelimiter();
  write(x.second);
}
template <class T>
void write(const complex<T>& x) {
  write(x.real());
  writeDelimiter();
  write(x.imag());
}
template <class T>
void write(const T& x);
template <class T, class... Ts>
void write(const T& x, Ts&&... xs);
template <class It>
typename enable_if<is_iterator<It>::value>::type write(It st, It en) {
  bool _first = 1;
  for (It _i = st; _i != en; _i++) {
    if (_first)
      _first = 0;
    else
      writeDelimiter();
    write(*_i);
  }
}
template <class It, class... Ts>
typename enable_if<is_iterator<It>::value>::type write(It st, It en,
                                                       Ts&&... xs) {
  write(st, en);
  writeDelimiter();
  write(forward<Ts>(xs)...);
}
template <class T>
void write(const T& x) {
  bool _first = 1;
  for (auto&& _i : x) {
    if (_first)
      _first = 0;
    else
      writeDelimiter();
    write(_i);
  }
}
template <class T, class... Ts>
void write(const T& x, Ts&&... xs) {
  write(x);
  writeDelimiter();
  write(forward<Ts>(xs)...);
}
void writeln() {
  (_outputBuffer[_outputPtr == _bufferSize
                     ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                        _outputPtr = 0)
                     : _outputPtr] = ('\n'),
   _outputPtr++);
}
template <class... Ts>
void writeln(Ts&&... xs) {
  write(forward<Ts>(xs)...);
  (_outputBuffer[_outputPtr == _bufferSize
                     ? (fwrite(_outputBuffer, 1, _outputPtr, _output),
                        _outputPtr = 0)
                     : _outputPtr] = ('\n'),
   _outputPtr++);
}
void flush() {
  do {
    (fwrite(_outputBuffer, 1, _outputPtr, _output), _outputPtr = 0);
    fflush(_output);
  } while (0);
}
class IOManager {
 public:
  ~IOManager() {
    flush();
    if (_tempInputBuf) delete[](_tempInputBuf);
  }
};
unique_ptr<IOManager> iomanager = _make_unique<IOManager>();
void setOutput(FILE* file) {
  flush();
  _output = file;
}
void setOutput(const char* second) {
  flush();
  _output = fopen(second, "w");
}
void setOutput(const string& second) {
  flush();
  _output = fopen(second.c_str(), "w");
}
template <class... Ts>
void debug(const Ts&... xs) {
  FILE* _temp = _output;
  setOutput(_error);
  write(xs...);
  setOutput(_temp);
}
template <class... Ts>
void debugln(const Ts&... xs) {
  FILE* _temp = _output;
  setOutput(_error);
  writeln(xs...);
  setOutput(_temp);
}
void setError(FILE* file) {
  flush();
  _error = file;
}
void setError(const char* second) {
  flush();
  _error = fopen(second, "w");
}
void setError(const string& second) {
  flush();
  _error = fopen(second.c_str(), "w");
}
const int MAXN = 1005;
int N, M, T, P[MAXN * 2], mate[MAXN * 2];
bool done[MAXN * 2];
int main() {
  read(N, M);
  fill(mate + 1, mate + 2 * N + 1, -1);
  fill(done + 1, done + 2 * N + 1, 0);
  read(P + 1, P + 2 * N + 1);
  int a, b;
  for (auto i = (0); i < (M); i++) {
    read(a, b);
    mate[a] = b;
    mate[b] = a;
  }
  read(T);
  if (T == 1) {
    for (auto it = (0); it < (N); it++) {
      int mxInd = -1, maxP = -1;
      for (auto i = (1); i < (2 * N + 1); i++) {
        if (!done[i] && mate[i] != -1 && P[i] > maxP) {
          maxP = P[i];
          mxInd = i;
        }
      }
      if (mxInd == -1) {
        for (auto i = (1); i < (2 * N + 1); i++) {
          if (!done[i] && P[i] > maxP) {
            maxP = P[i];
            mxInd = i;
          }
        }
      }
      assert(mxInd != -1);
      writeln(mxInd);
      flush();
      done[mxInd] = 1;
      int x;
      read(x);
      done[x] = 1;
    }
  } else {
    for (auto it = (0); it < (N); it++) {
      int x;
      read(x);
      done[x] = 1;
      if (mate[x] != -1 && !done[mate[x]]) {
        writeln(mate[x]);
        flush();
        done[mate[x]] = 1;
      } else {
        int mxInd = -1, maxP = -1;
        for (auto i = (1); i < (2 * N + 1); i++) {
          if (!done[i] && mate[i] != -1 && P[i] > maxP) {
            maxP = P[i];
            mxInd = i;
          }
        }
        if (mxInd == -1) {
          for (auto i = (1); i < (2 * N + 1); i++) {
            if (!done[i] && P[i] > maxP) {
              maxP = P[i];
              mxInd = i;
            }
          }
        }
        assert(mxInd != -1);
        writeln(mxInd);
        flush();
        done[mxInd] = 1;
      }
    }
  }
  return 0;
}
