#include <bits/stdc++.h>
using namespace std;
template <typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using maxpq = priority_queue<T, vector<T>, less<T>>;
template <typename T1, typename T2, typename H1 = hash<T1>,
          typename H2 = hash<T2>>
struct pair_hash {
  size_t operator()(const pair<T1, T2>& p) const {
    return 31 * H1{}(p.first) + H2{}(p.second);
  }
};
char _inputBuffer[4096 + 1], *_inputPtr = _inputBuffer, _outputBuffer[4096], _c,
                             _sign, *_tempInputBuf = nullptr, _numBuf[128],
                             _tempOutputBuf[128], _fill = ' ';
const char* _delimiter = " ";
int _cur, _outputPtr = 0, _numPtr = 0, _precision = 6, _width = 0,
          _tempOutputPtr = 0, _cnt;
unsigned long long _precisionBase = 1000000;
void read(int& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign)
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    for ((x) -= '0';
         (_c = (*_inputPtr ? *_inputPtr++
                           : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                             4096, stdin)] = '\0',
                                   *_inputPtr++))) >= '0';
         (x) = (x)*10 + _c - '0')
      ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(unsigned int& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign)
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    for ((x) -= '0';
         (_c = (*_inputPtr ? *_inputPtr++
                           : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                             4096, stdin)] = '\0',
                                   *_inputPtr++))) >= '0';
         (x) = (x)*10 + _c - '0')
      ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(long long& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign)
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    for ((x) -= '0';
         (_c = (*_inputPtr ? *_inputPtr++
                           : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                             4096, stdin)] = '\0',
                                   *_inputPtr++))) >= '0';
         (x) = (x)*10 + _c - '0')
      ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(unsigned long long& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign)
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    for ((x) -= '0';
         (_c = (*_inputPtr ? *_inputPtr++
                           : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                             4096, stdin)] = '\0',
                                   *_inputPtr++))) >= '0';
         (x) = (x)*10 + _c - '0')
      ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(double& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign)
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    for ((x) -= '0';
         (_c = (*_inputPtr ? *_inputPtr++
                           : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                             4096, stdin)] = '\0',
                                   *_inputPtr++))) >= '0';
         (x) = (x)*10 + _c - '0')
      ;
    if (_c == '.')
      for (double _div = 1.0;
           (_c = (*_inputPtr ? *_inputPtr++
                             : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                               4096, stdin)] = '\0',
                                     *_inputPtr++))) >= '0';
           (x) += (_c - '0') / (_div *= 10))
        ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(long double& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign)
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    for ((x) -= '0';
         (_c = (*_inputPtr ? *_inputPtr++
                           : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                             4096, stdin)] = '\0',
                                   *_inputPtr++))) >= '0';
         (x) = (x)*10 + _c - '0')
      ;
    if (_c == '.')
      for (long double _div = 1.0;
           (_c = (*_inputPtr ? *_inputPtr++
                             : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                               4096, stdin)] = '\0',
                                     *_inputPtr++))) >= '0';
           (x) += (_c - '0') / (_div *= 10))
        ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(char& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
  } while (0);
}
void read(char* x) {
  do {
    _cur = 0;
    do {
      _c = (*_inputPtr ? *_inputPtr++
                       : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                             stdin)] = '\0',
                          *_inputPtr++));
    } while (_c <= ' ');
    do {
      (x)[_cur++] = _c;
    } while ((_c = (*_inputPtr ? *_inputPtr++
                               : (_inputBuffer[fread(_inputPtr = _inputBuffer,
                                                     1, 4096, stdin)] = '\0',
                                  *_inputPtr++))) > ' ');
    (x)[_cur] = '\0';
  } while (0);
}
void read(string& x) {
  do {
    if (!_tempInputBuf) assert(0);
    do {
      _cur = 0;
      do {
        _c = (*_inputPtr ? *_inputPtr++
                         : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                                               4096, stdin)] = '\0',
                            *_inputPtr++));
      } while (_c <= ' ');
      do {
        (_tempInputBuf)[_cur++] = _c;
      } while ((_c = (*_inputPtr ? *_inputPtr++
                                 : (_inputBuffer[fread(_inputPtr = _inputBuffer,
                                                       1, 4096, stdin)] = '\0',
                                    *_inputPtr++))) > ' ');
      (_tempInputBuf)[_cur] = '\0';
    } while (0);
    (x) = string(_tempInputBuf, _cur);
  } while (0);
}
template <typename T, typename... Ts>
void read(T&& x, Ts&&... xs) {
  read(x);
  read(forward<Ts>(xs)...);
}
void write(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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(int x) {
  do {
    if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      _cnt = 0;
      for (unsigned int _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 (unsigned int _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(unsigned int x) {
  do {
    if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      _cnt = 0;
      for (unsigned int _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 (unsigned int _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(long long x) {
  do {
    if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      _cnt = 0;
      for (unsigned long long _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 (unsigned long long _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(unsigned long long x) {
  do {
    if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      _cnt = 0;
      for (unsigned long long _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 (unsigned long long _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(double x) {
  do {
    if (std::isnan(x)) {
      do {
        int _slen = strlen("NaN");
        for (int _i = 0; _i < (_width - _slen); _i++)
          (_outputBuffer[_outputPtr == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
        for (const char* _p = ("NaN"); *_p;
             (_outputBuffer[_outputPtr == 4096
                                ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                   _outputPtr = 0)
                                : _outputPtr] = (*_p++),
                                  _outputPtr++))
          ;
        for (int _i = 0; _i < (-_width - _slen); _i++)
          (_outputBuffer[_outputPtr == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _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 == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
        for (const char* _p = ("Inf"); *_p;
             (_outputBuffer[_outputPtr == 4096
                                ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                   _outputPtr = 0)
                                : _outputPtr] = (*_p++),
                                  _outputPtr++))
          ;
        for (int _i = 0; _i < (-_width - _slen); _i++)
          (_outputBuffer[_outputPtr == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
      } while (0);
    } else if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      unsigned long long _I = (unsigned long long)(-(x));
      unsigned long long _F = ((-(x)) - _I) * _precisionBase + (double)(0.5);
      if (_F >= _precisionBase) {
        _I++;
        _F = 0;
      }
      _cnt = 0;
      for (unsigned long long _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 (unsigned long long _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 {
      unsigned long long _I = (unsigned long long)(x);
      unsigned long long _F = ((x)-_I) * _precisionBase + (double)(0.5);
      if (_F >= _precisionBase) {
        _I++;
        _F = 0;
      }
      _cnt = 0;
      for (unsigned long long _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 (unsigned long long _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(long double x) {
  do {
    if (std::isnan(x)) {
      do {
        int _slen = strlen("NaN");
        for (int _i = 0; _i < (_width - _slen); _i++)
          (_outputBuffer[_outputPtr == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
        for (const char* _p = ("NaN"); *_p;
             (_outputBuffer[_outputPtr == 4096
                                ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                   _outputPtr = 0)
                                : _outputPtr] = (*_p++),
                                  _outputPtr++))
          ;
        for (int _i = 0; _i < (-_width - _slen); _i++)
          (_outputBuffer[_outputPtr == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _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 == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
        for (const char* _p = ("Inf"); *_p;
             (_outputBuffer[_outputPtr == 4096
                                ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                   _outputPtr = 0)
                                : _outputPtr] = (*_p++),
                                  _outputPtr++))
          ;
        for (int _i = 0; _i < (-_width - _slen); _i++)
          (_outputBuffer[_outputPtr == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
      } while (0);
    } else if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      unsigned long long _I = (unsigned long long)(-(x));
      unsigned long long _F =
          ((-(x)) - _I) * _precisionBase + (long double)(0.5);
      if (_F >= _precisionBase) {
        _I++;
        _F = 0;
      }
      _cnt = 0;
      for (unsigned long long _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 (unsigned long long _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 {
      unsigned long long _I = (unsigned long long)(x);
      unsigned long long _F = ((x)-_I) * _precisionBase + (long double)(0.5);
      if (_F >= _precisionBase) {
        _I++;
        _F = 0;
      }
      _cnt = 0;
      for (unsigned long long _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 (unsigned long long _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(char x) {
  do {
    (_tempOutputBuf[_tempOutputPtr++] = (x));
    int _tempLen = _tempOutputPtr;
    for (int _i = 0; _i < (_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(char* x) {
  do {
    int _slen = strlen(x);
    for (int _i = 0; _i < (_width - _slen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (const char* _p = (x); *_p;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (*_p++),
                              _outputPtr++))
      ;
    for (int _i = 0; _i < (-_width - _slen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (const char* _p = (x); *_p;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (*_p++),
                              _outputPtr++))
      ;
    for (int _i = 0; _i < (-_width - _slen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(string& x) {
  do {
    for (int _i = 0; _i < (_width - (int)(x).length()); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < (int)(x).length();
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (x[_i++]),
                              _outputPtr++))
      ;
    for (int _i = 0; _i < (-_width - (int)(x).length()); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
template <typename T, typename... Ts>
void write(T&& x, Ts&&... xs) {
  write(x);
  for (const char* _p = _delimiter; *_p;
       (_outputBuffer[_outputPtr == 4096
                          ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                             _outputPtr = 0)
                          : _outputPtr] = (*_p++),
                            _outputPtr++))
    ;
  write(forward<Ts>(xs)...);
}
void writeln() {
  (_outputBuffer[_outputPtr == 4096
                     ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                        _outputPtr = 0)
                     : _outputPtr] = ('\n'),
   _outputPtr++);
}
template <typename... Ts>
void writeln(Ts&&... xs) {
  write(forward<Ts>(xs)...);
  (_outputBuffer[_outputPtr == 4096
                     ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                        _outputPtr = 0)
                     : _outputPtr] = ('\n'),
   _outputPtr++);
}
void flush() {
  do {
    (fwrite(_outputBuffer, 1, _outputPtr, stdout), _outputPtr = 0);
    fflush(stdout);
  } while (0);
}
class IOManager {
 public:
  ~IOManager() { flush(); }
};
unique_ptr<IOManager> _iomanager;
int N, K, grid[4][55];
pair<int, int> ord[55 * 2];
int main() {
  _iomanager.reset(new IOManager());
  read(N, K);
  for (auto i = (0); i < (4); i++)
    for (auto j = (0); j < (N); j++) read(grid[i][j]);
  for (auto i = (0); i < (N); i++) {
    ord[i] = {1, i};
    ord[N + i] = {2, N - i - 1};
  }
  vector<pair<int, pair<int, int>>> moves;
  int done = 0;
  while (true) {
    int startInd = -1;
    for (auto i = (0); i < (2 * N); i++) {
      if (grid[ord[i].first][ord[i].second] != 0 &&
          grid[ord[i].first][ord[i].second] ==
              grid[ord[i].first ^ 1][ord[i].second]) {
        moves.push_back({grid[ord[i].first][ord[i].second],
                         {ord[i].first ^ 1, ord[i].second}});
        grid[ord[i].first][ord[i].second] = 0;
        done++;
      }
      if (grid[ord[i].first][ord[i].second] == 0) startInd = i;
    }
    if (startInd == -1 || done == K) break;
    for (auto h = (0); h < (2 * N - 1); h++) {
      int i = (startInd + h) % (2 * N);
      if (grid[ord[(i + 1) % (2 * N)].first][ord[(i + 1) % (2 * N)].second] ==
          0)
        continue;
      grid[ord[i].first][ord[i].second] =
          grid[ord[(i + 1) % (2 * N)].first][ord[(i + 1) % (2 * N)].second];
      moves.push_back(
          {grid[ord[i].first][ord[i].second], {ord[i].first, ord[i].second}});
      grid[ord[(i + 1) % (2 * N)].first][ord[(i + 1) % (2 * N)].second] = 0;
    }
  }
  if (done != K)
    writeln(-1);
  else {
    writeln(((int)(moves).size()));
    for (pair<int, pair<int, int>> x : moves)
      writeln(x.first, x.second.first + 1, x.second.second + 1);
  }
  return 0;
}

### Prompt

Create a solution in CPP for the following problem:

Allen dreams of one day owning a enormous fleet of electric cars, the car of the future! He knows that this will give him a big status boost. As Allen is planning out all of the different types of cars he will own and how he will arrange them, he realizes that he has a problem. 

Allen's future parking lot can be represented as a rectangle with 4 rows and n (n ≤ 50) columns of rectangular spaces, each of which can contain at most one car at any time. He imagines having k (k ≤ 2n) cars in the grid, and all the cars are initially in the second and third rows. Each of the cars also has a different designated parking space in the first or fourth row. Allen has to put the cars into corresponding parking places.

<image> Illustration to the first example.

However, since Allen would never entrust his cars to anyone else, only one car can be moved at a time. He can drive a car from a space in any of the four cardinal directions to a neighboring empty space. Furthermore, Allen can only move one of his cars into a space on the first or fourth rows if it is the car's designated parking space. 

Allen knows he will be a very busy man, and will only have time to move cars at most 20000 times before he realizes that moving cars is not worth his time. Help Allen determine if he should bother parking his cars or leave it to someone less important.

Input

The first line of the input contains two space-separated integers n and k (1 ≤ n ≤ 50, 1 ≤ k ≤ 2n), representing the number of columns and the number of cars, respectively.

The next four lines will contain n integers each between 0 and k inclusive, representing the initial state of the parking lot. The rows are numbered 1 to 4 from top to bottom and the columns are numbered 1 to n from left to right.

In the first and last line, an integer 1 ≤ x ≤ k represents a parking spot assigned to car x (you can only move this car to this place), while the integer 0 represents a empty space (you can't move any car to this place).

In the second and third line, an integer 1 ≤ x ≤ k represents initial position of car x, while the integer 0 represents an empty space (you can move any car to this place).

Each x between 1 and k appears exactly once in the second and third line, and exactly once in the first and fourth line.

Output

If there is a sequence of moves that brings all of the cars to their parking spaces, with at most 20000 car moves, then print m, the number of moves, on the first line. On the following m lines, print the moves (one move per line) in the format i r c, which corresponds to Allen moving car i to the neighboring space at row r and column c.

If it is not possible for Allen to move all the cars to the correct spaces with at most 20000 car moves, print a single line with the integer -1.

Examples

Input

4 5
1 2 0 4
1 2 0 4
5 0 0 3
0 5 0 3


Output

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


Input

1 2
1
2
1
2


Output

-1


Input

1 2
1
1
2
2


Output

2
1 1 1
2 4 1

Note

In the first sample test case, all cars are in front of their spots except car 5, which is in front of the parking spot adjacent. The example shows the shortest possible sequence of moves, but any sequence of length at most 20000 will be accepted.

In the second sample test case, there is only one column, and the cars are in the wrong order, so no cars can move and the task is impossible.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using maxpq = priority_queue<T, vector<T>, less<T>>;
template <typename T1, typename T2, typename H1 = hash<T1>,
          typename H2 = hash<T2>>
struct pair_hash {
  size_t operator()(const pair<T1, T2>& p) const {
    return 31 * H1{}(p.first) + H2{}(p.second);
  }
};
char _inputBuffer[4096 + 1], *_inputPtr = _inputBuffer, _outputBuffer[4096], _c,
                             _sign, *_tempInputBuf = nullptr, _numBuf[128],
                             _tempOutputBuf[128], _fill = ' ';
const char* _delimiter = " ";
int _cur, _outputPtr = 0, _numPtr = 0, _precision = 6, _width = 0,
          _tempOutputPtr = 0, _cnt;
unsigned long long _precisionBase = 1000000;
void read(int& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign)
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    for ((x) -= '0';
         (_c = (*_inputPtr ? *_inputPtr++
                           : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                             4096, stdin)] = '\0',
                                   *_inputPtr++))) >= '0';
         (x) = (x)*10 + _c - '0')
      ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(unsigned int& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign)
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    for ((x) -= '0';
         (_c = (*_inputPtr ? *_inputPtr++
                           : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                             4096, stdin)] = '\0',
                                   *_inputPtr++))) >= '0';
         (x) = (x)*10 + _c - '0')
      ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(long long& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign)
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    for ((x) -= '0';
         (_c = (*_inputPtr ? *_inputPtr++
                           : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                             4096, stdin)] = '\0',
                                   *_inputPtr++))) >= '0';
         (x) = (x)*10 + _c - '0')
      ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(unsigned long long& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign)
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    for ((x) -= '0';
         (_c = (*_inputPtr ? *_inputPtr++
                           : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                             4096, stdin)] = '\0',
                                   *_inputPtr++))) >= '0';
         (x) = (x)*10 + _c - '0')
      ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(double& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign)
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    for ((x) -= '0';
         (_c = (*_inputPtr ? *_inputPtr++
                           : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                             4096, stdin)] = '\0',
                                   *_inputPtr++))) >= '0';
         (x) = (x)*10 + _c - '0')
      ;
    if (_c == '.')
      for (double _div = 1.0;
           (_c = (*_inputPtr ? *_inputPtr++
                             : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                               4096, stdin)] = '\0',
                                     *_inputPtr++))) >= '0';
           (x) += (_c - '0') / (_div *= 10))
        ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(long double& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
    _sign = (x) == '-';
    if (_sign)
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    for ((x) -= '0';
         (_c = (*_inputPtr ? *_inputPtr++
                           : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                             4096, stdin)] = '\0',
                                   *_inputPtr++))) >= '0';
         (x) = (x)*10 + _c - '0')
      ;
    if (_c == '.')
      for (long double _div = 1.0;
           (_c = (*_inputPtr ? *_inputPtr++
                             : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                               4096, stdin)] = '\0',
                                     *_inputPtr++))) >= '0';
           (x) += (_c - '0') / (_div *= 10))
        ;
    if (_sign) (x) = -(x);
  } while (0);
}
void read(char& x) {
  do {
    do {
      (x) = (*_inputPtr ? *_inputPtr++
                        : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                              stdin)] = '\0',
                           *_inputPtr++));
    } while ((x) <= ' ');
  } while (0);
}
void read(char* x) {
  do {
    _cur = 0;
    do {
      _c = (*_inputPtr ? *_inputPtr++
                       : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1, 4096,
                                             stdin)] = '\0',
                          *_inputPtr++));
    } while (_c <= ' ');
    do {
      (x)[_cur++] = _c;
    } while ((_c = (*_inputPtr ? *_inputPtr++
                               : (_inputBuffer[fread(_inputPtr = _inputBuffer,
                                                     1, 4096, stdin)] = '\0',
                                  *_inputPtr++))) > ' ');
    (x)[_cur] = '\0';
  } while (0);
}
void read(string& x) {
  do {
    if (!_tempInputBuf) assert(0);
    do {
      _cur = 0;
      do {
        _c = (*_inputPtr ? *_inputPtr++
                         : (_inputBuffer[fread(_inputPtr = _inputBuffer, 1,
                                               4096, stdin)] = '\0',
                            *_inputPtr++));
      } while (_c <= ' ');
      do {
        (_tempInputBuf)[_cur++] = _c;
      } while ((_c = (*_inputPtr ? *_inputPtr++
                                 : (_inputBuffer[fread(_inputPtr = _inputBuffer,
                                                       1, 4096, stdin)] = '\0',
                                    *_inputPtr++))) > ' ');
      (_tempInputBuf)[_cur] = '\0';
    } while (0);
    (x) = string(_tempInputBuf, _cur);
  } while (0);
}
template <typename T, typename... Ts>
void read(T&& x, Ts&&... xs) {
  read(x);
  read(forward<Ts>(xs)...);
}
void write(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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(int x) {
  do {
    if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      _cnt = 0;
      for (unsigned int _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 (unsigned int _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(unsigned int x) {
  do {
    if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      _cnt = 0;
      for (unsigned int _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 (unsigned int _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(long long x) {
  do {
    if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      _cnt = 0;
      for (unsigned long long _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 (unsigned long long _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(unsigned long long x) {
  do {
    if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      _cnt = 0;
      for (unsigned long long _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 (unsigned long long _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(double x) {
  do {
    if (std::isnan(x)) {
      do {
        int _slen = strlen("NaN");
        for (int _i = 0; _i < (_width - _slen); _i++)
          (_outputBuffer[_outputPtr == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
        for (const char* _p = ("NaN"); *_p;
             (_outputBuffer[_outputPtr == 4096
                                ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                   _outputPtr = 0)
                                : _outputPtr] = (*_p++),
                                  _outputPtr++))
          ;
        for (int _i = 0; _i < (-_width - _slen); _i++)
          (_outputBuffer[_outputPtr == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _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 == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
        for (const char* _p = ("Inf"); *_p;
             (_outputBuffer[_outputPtr == 4096
                                ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                   _outputPtr = 0)
                                : _outputPtr] = (*_p++),
                                  _outputPtr++))
          ;
        for (int _i = 0; _i < (-_width - _slen); _i++)
          (_outputBuffer[_outputPtr == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
      } while (0);
    } else if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      unsigned long long _I = (unsigned long long)(-(x));
      unsigned long long _F = ((-(x)) - _I) * _precisionBase + (double)(0.5);
      if (_F >= _precisionBase) {
        _I++;
        _F = 0;
      }
      _cnt = 0;
      for (unsigned long long _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 (unsigned long long _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 {
      unsigned long long _I = (unsigned long long)(x);
      unsigned long long _F = ((x)-_I) * _precisionBase + (double)(0.5);
      if (_F >= _precisionBase) {
        _I++;
        _F = 0;
      }
      _cnt = 0;
      for (unsigned long long _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 (unsigned long long _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(long double x) {
  do {
    if (std::isnan(x)) {
      do {
        int _slen = strlen("NaN");
        for (int _i = 0; _i < (_width - _slen); _i++)
          (_outputBuffer[_outputPtr == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
        for (const char* _p = ("NaN"); *_p;
             (_outputBuffer[_outputPtr == 4096
                                ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                   _outputPtr = 0)
                                : _outputPtr] = (*_p++),
                                  _outputPtr++))
          ;
        for (int _i = 0; _i < (-_width - _slen); _i++)
          (_outputBuffer[_outputPtr == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _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 == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
        for (const char* _p = ("Inf"); *_p;
             (_outputBuffer[_outputPtr == 4096
                                ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                   _outputPtr = 0)
                                : _outputPtr] = (*_p++),
                                  _outputPtr++))
          ;
        for (int _i = 0; _i < (-_width - _slen); _i++)
          (_outputBuffer[_outputPtr == 4096
                             ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                                _outputPtr = 0)
                             : _outputPtr] = (_fill),
           _outputPtr++);
      } while (0);
    } else if ((x) < 0) {
      (_tempOutputBuf[_tempOutputPtr++] = ('-'));
      unsigned long long _I = (unsigned long long)(-(x));
      unsigned long long _F =
          ((-(x)) - _I) * _precisionBase + (long double)(0.5);
      if (_F >= _precisionBase) {
        _I++;
        _F = 0;
      }
      _cnt = 0;
      for (unsigned long long _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 (unsigned long long _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 {
      unsigned long long _I = (unsigned long long)(x);
      unsigned long long _F = ((x)-_I) * _precisionBase + (long double)(0.5);
      if (_F >= _precisionBase) {
        _I++;
        _F = 0;
      }
      _cnt = 0;
      for (unsigned long long _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 (unsigned long long _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(char x) {
  do {
    (_tempOutputBuf[_tempOutputPtr++] = (x));
    int _tempLen = _tempOutputPtr;
    for (int _i = 0; _i < (_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < _tempOutputPtr;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (_tempOutputBuf[_i++]),
                              _outputPtr++))
      ;
    _tempOutputPtr = 0;
    for (int _i = 0; _i < (-_width - _tempLen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(char* x) {
  do {
    int _slen = strlen(x);
    for (int _i = 0; _i < (_width - _slen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (const char* _p = (x); *_p;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (*_p++),
                              _outputPtr++))
      ;
    for (int _i = 0; _i < (-_width - _slen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _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 == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (const char* _p = (x); *_p;
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (*_p++),
                              _outputPtr++))
      ;
    for (int _i = 0; _i < (-_width - _slen); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
void write(string& x) {
  do {
    for (int _i = 0; _i < (_width - (int)(x).length()); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
    for (int _i = 0; _i < (int)(x).length();
         (_outputBuffer[_outputPtr == 4096
                            ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                               _outputPtr = 0)
                            : _outputPtr] = (x[_i++]),
                              _outputPtr++))
      ;
    for (int _i = 0; _i < (-_width - (int)(x).length()); _i++)
      (_outputBuffer[_outputPtr == 4096
                         ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                            _outputPtr = 0)
                         : _outputPtr] = (_fill),
       _outputPtr++);
  } while (0);
}
template <typename T, typename... Ts>
void write(T&& x, Ts&&... xs) {
  write(x);
  for (const char* _p = _delimiter; *_p;
       (_outputBuffer[_outputPtr == 4096
                          ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                             _outputPtr = 0)
                          : _outputPtr] = (*_p++),
                            _outputPtr++))
    ;
  write(forward<Ts>(xs)...);
}
void writeln() {
  (_outputBuffer[_outputPtr == 4096
                     ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                        _outputPtr = 0)
                     : _outputPtr] = ('\n'),
   _outputPtr++);
}
template <typename... Ts>
void writeln(Ts&&... xs) {
  write(forward<Ts>(xs)...);
  (_outputBuffer[_outputPtr == 4096
                     ? (fwrite(_outputBuffer, 1, _outputPtr, stdout),
                        _outputPtr = 0)
                     : _outputPtr] = ('\n'),
   _outputPtr++);
}
void flush() {
  do {
    (fwrite(_outputBuffer, 1, _outputPtr, stdout), _outputPtr = 0);
    fflush(stdout);
  } while (0);
}
class IOManager {
 public:
  ~IOManager() { flush(); }
};
unique_ptr<IOManager> _iomanager;
int N, K, grid[4][55];
pair<int, int> ord[55 * 2];
int main() {
  _iomanager.reset(new IOManager());
  read(N, K);
  for (auto i = (0); i < (4); i++)
    for (auto j = (0); j < (N); j++) read(grid[i][j]);
  for (auto i = (0); i < (N); i++) {
    ord[i] = {1, i};
    ord[N + i] = {2, N - i - 1};
  }
  vector<pair<int, pair<int, int>>> moves;
  int done = 0;
  while (true) {
    int startInd = -1;
    for (auto i = (0); i < (2 * N); i++) {
      if (grid[ord[i].first][ord[i].second] != 0 &&
          grid[ord[i].first][ord[i].second] ==
              grid[ord[i].first ^ 1][ord[i].second]) {
        moves.push_back({grid[ord[i].first][ord[i].second],
                         {ord[i].first ^ 1, ord[i].second}});
        grid[ord[i].first][ord[i].second] = 0;
        done++;
      }
      if (grid[ord[i].first][ord[i].second] == 0) startInd = i;
    }
    if (startInd == -1 || done == K) break;
    for (auto h = (0); h < (2 * N - 1); h++) {
      int i = (startInd + h) % (2 * N);
      if (grid[ord[(i + 1) % (2 * N)].first][ord[(i + 1) % (2 * N)].second] ==
          0)
        continue;
      grid[ord[i].first][ord[i].second] =
          grid[ord[(i + 1) % (2 * N)].first][ord[(i + 1) % (2 * N)].second];
      moves.push_back(
          {grid[ord[i].first][ord[i].second], {ord[i].first, ord[i].second}});
      grid[ord[(i + 1) % (2 * N)].first][ord[(i + 1) % (2 * N)].second] = 0;
    }
  }
  if (done != K)
    writeln(-1);
  else {
    writeln(((int)(moves).size()));
    for (pair<int, pair<int, int>> x : moves)
      writeln(x.first, x.second.first + 1, x.second.second + 1);
  }
  return 0;
}

```