Kod źródłowy zgłoszenia nr 157044

// Generated by include.py
// Jakub Staroń, 2016
// For more info see https://github.com/staronj/ProgrammingContestsLibrary
// Jakub Staroń, 2016

// Jakub Staroń, 2016

#include <iostream>
#include <sstream>
#include <iterator>
#include <type_traits>
#include <algorithm>
#include <memory>
#include <utility>
#include <functional>
#include <bitset>
#include <vector>
#include <array>
#include <list>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cinttypes>
#include <ctime>
#include <cctype>
#include <cstring>
#include <random>
#include <cassert>

namespace lib {

using int8    = std::int8_t;
using uint8   = std::uint8_t;
using int16   = std::int16_t;
using uint16  = std::uint16_t;
using int32   = std::int32_t;
using uint32  = std::uint32_t;
using int64   = std::int64_t;
using uint64  = std::uint64_t;

/**
 * Random number generator. Returns 32 bits numbers.
 *
 * You should prefer this random number generator over
 * C's rand(), because rand() max range is not strictly
 * defined and can be supringsly small (like 10000).
 */
std::knuth_b Random(time(0));

/**
 * 32 bits random generator.
 */
uint32 Random32() {
  return Random();
}

/**
 * 64 bits random generator.
 */
uint64 Random64() {
  return uint64(Random32()) << 32 | uint64(Random32());
}

#ifdef __SIZEOF_INT128__
#define HAVE_INT128_TYPES
#endif

#define USE_INT128_TYPES_IF_AVAILABLE 0

#if defined(HAVE_INT128_TYPES) && USE_INT128_TYPES_IF_AVAILABLE
#define USE_INT128_TYPES
#endif

#ifdef USE_INT128_TYPES
using int128 = __int128;
using uint128 = unsigned __int128;
#endif

using bit_vector = std::vector<bool>;

using char_pair     = std::pair<char, char>;
using bool_pair     = std::pair<bool, bool>;
using int32_pair    = std::pair<int32, int32>;
using uint32_pair   = std::pair<uint32, uint32>;
using int64_pair    = std::pair<int64, int64>;
using uint64_pair   = std::pair<uint64, uint64>;

} // namespace lib
// Jakub Staroń, 2016

// Jakub Staroń, 2016


namespace lib {

// post-incrementation -> pre-incrementation
template <typename T>
inline T operator++(T& obj, int) {
  T temp = obj;
  ++obj;
  return temp;
}

// post-decrementation -> pre-decrementation
template <typename T>
inline T operator--(T& obj, int) {
  T temp = obj;
  --obj;
  return temp;
}

// obj += n -> obj + n
template <typename T, typename Integral>
inline typename std::enable_if<std::is_integral<Integral>::value, T&>::type
operator+=(T& obj, Integral n) {
  obj = obj + n;
  return obj;
}

// obj1 += obj2 -> obj1 + obj2
template <typename T>
inline T& operator+=(T& obj1, const T& obj2) {
  obj1 = obj1 + obj2;
  return obj1;
}

// obj -= n -> obj - n
template <typename T, typename Integral>
inline typename std::enable_if<std::is_integral<Integral>::value, T&>::type
operator-=(T& obj, Integral n) {
  obj = obj - n;
  return obj;
}

// obj1 -= obj2 -> obj1 - obj2
template <typename T>
inline T& operator-=(T& obj1, const T& obj2) {
  obj1 = obj1 - obj2;
  return obj1;
}

// obj *= n -> obj * n
template <typename T, typename Integral>
inline typename std::enable_if<std::is_integral<Integral>::value, T&>::type
operator*=(T& obj, Integral n) {
  obj = obj * n;
  return obj;
}

// obj1 *= obj2 -> obj1 * obj2
template <typename T>
inline T& operator*=(T& obj1, const T& obj2) {
  obj1 = obj1 * obj2;
  return obj1;
}

// obj %= n -> obj % n
template <typename T, typename Integral>
inline typename std::enable_if<std::is_integral<Integral>::value, T&>::type
operator%=(T& obj, Integral n) {
  obj = obj % n;
  return obj;
}

// obj1 %= obj2 -> obj1 % obj2
template <typename T>
inline T& operator%=(T& obj1, const T& obj2) {
  obj1 = obj1 % obj2;
  return obj1;
}

// n + obj -> obj + n
template <typename T, typename Integral>
inline typename std::enable_if<std::is_integral<Integral>::value, T>::type
operator+(Integral n, const T& obj) {
  return obj + n;
}

// n * obj -> obj * n
template <typename T, typename Integral>
inline typename std::enable_if<std::is_integral<Integral>::value, T>::type
operator*(Integral n, const T& obj) {
  return obj * n;
}

// obj - n -> obj + (-n)
template <typename T, typename Integral>
inline typename std::enable_if<std::is_signed<Integral>::value, T>::type
operator-(const T& obj, Integral n) {
  return obj + (-n);
}

// obj -= n -> obj += (-n)
template <typename T, typename Integral>
inline typename std::enable_if<std::is_signed<Integral>::value, T&>::type
operator-=(const T& obj, Integral n) {
  return obj += (-n);
}

// lhs > rhs -> rhs < lhs
template <typename T>
inline bool operator>(const T& lhs, const T& rhs) {
  return rhs < lhs;
}

// lhs <= rhs -> !(rhs < lhs)
template <typename T>
inline bool operator<=(const T& lhs, const T& rhs) {
  return !(rhs < lhs);
}

// lhs >= rhs -> !(rhs < lhs)
template <typename T>
inline bool operator>=(const T& lhs, const T& rhs) {
  return rhs <= lhs;
}

// lhs >= rhs -> !(rhs < lhs)
template <typename T>
inline bool operator!=(const T& lhs, const T& rhs) {
  return !(lhs == rhs);
}

// + for pairs
template <typename Integral1, typename Integral2>
constexpr std::pair<Integral1, Integral2> operator+(const std::pair<Integral1, Integral2>& lhs, const std::pair<Integral1, Integral2>& rhs) {
  return std::pair<Integral1, Integral2>(lhs.first + rhs.first, lhs.second + rhs.second);
}

// - for pairs
template <typename Integral1, typename Integral2>
constexpr std::pair<Integral1, Integral2> operator-(const std::pair<Integral1, Integral2>& lhs, const std::pair<Integral1, Integral2>& rhs) {
  return std::pair<Integral1, Integral2>(lhs.first - rhs.first, lhs.second - rhs.second);
}

// % for pairs
template <typename Integral1, typename Integral2>
constexpr std::pair<Integral1, Integral2> operator%(const std::pair<Integral1, Integral2>& lhs, const std::pair<Integral1, Integral2>& rhs) {
  return std::pair<Integral1, Integral2>(lhs.first % rhs.first, lhs.second % rhs.second);
}

// * for pairs
template <typename Integral1, typename Integral2>
constexpr std::pair<Integral1, Integral2> operator*(const std::pair<Integral1, Integral2>& lhs, const std::pair<Integral1, Integral2>& rhs) {
  return std::pair<Integral1, Integral2>(lhs.first * rhs.first, lhs.second * rhs.second);
}

// % for (pair, Integral)
template <typename Integral1, typename Integral2, typename Integral3>
constexpr std::pair<Integral1, Integral2> operator%(const std::pair<Integral1, Integral2>& lhs, const Integral3& rhs) {
  return std::pair<Integral1, Integral2>(lhs.first % rhs, lhs.second % rhs);
}

// * for (pair, Integral)
template <typename Integral1, typename Integral2, typename Integral3>
constexpr std::pair<Integral1, Integral2> operator*(const std::pair<Integral1, Integral2>& lhs, const Integral3& rhs) {
  return std::pair<Integral1, Integral2>(lhs.first * rhs, lhs.second * rhs);
}


} // namespace lib

namespace lib {

/**
 * type_traits-like predicate. Equal to true_type if argument is iterator.
 *
 * Example:
 * <pre>
 * static_assert(is_iterator<std::vector<int>::iterator>::value, "vector iterator is not iterator! help!");
 * </pre>
 */
template<typename Iterator>
struct is_iterator {
private:
  template<typename I> static constexpr auto test(int)
  -> decltype(
      *std::declval<const I>(),
      std::declval<const I>() == std::declval<const I>(),
      std::declval<const I>() != std::declval<const I>(),
      ++ std::declval<I&>(),
      std::declval<I&>() ++,
      std::iterator_traits<I>(),
      bool()) { return
        std::is_destructible<I>::value;
  }

  template<typename I> static constexpr bool test(...) { return false; }

public:
  static constexpr bool value = test<Iterator>(0);
};

/**
 * type_traits-like predicate. Equal to true_type if argument is iteratorable.
 *
 * Example:
 * <pre>
 * static_assert(is_iteratorable<std::vector<int>>::value, "vector should be iterable!");
 * </pre>
 */
template<typename T>
struct is_iterable {
  template <typename C>
  using begin_t = decltype(std::begin(std::declval<C&>()));

  template <typename C>
  using end_t = decltype(std::end(std::declval<C&>()));

  template<typename I> static constexpr auto test(int)
  -> decltype(
      std::declval<begin_t<I>>(),
      std::declval<end_t<I>>(),
      bool()) { return
        std::is_same<begin_t<I>, end_t<I>>::value &&
        is_iterator<begin_t<I>>::value;
  }

  template<typename I> static constexpr bool test(...) { return false; }

public:
  static constexpr bool value = test<T>(0);
};

/**
 * Random access iterator for iterating over integral type.
 *
 * Example:
 * <pre>
 * std::vector<int> v(counting_iterator<int>(0), counting_iterator<int>(5));
 * </pre>
 *
 * Produces v with elements {0, 1, 2, 3, 4}
 */
template <typename Integral>
class counting_iterator {
public:
  static_assert(std::is_integral<Integral>::value, "counting_iterator's template argument should be integral");
  using self_type = counting_iterator;
  using value_type = Integral;
  using reference = const value_type&;
  using pointer = const value_type*;
  using difference_type = typename std::make_signed<Integral>::type;
  using iterator_category = std::random_access_iterator_tag;

  counting_iterator(): value_() { }

  explicit counting_iterator(Integral n): value_(n) { }

  reference operator*() const {
    return value_;
  }

  self_type& operator++() {
    ++value_;
    return *this;
  }

  self_type& operator--() {
    --value_;
    return *this;
  }

  self_type& operator+=(difference_type n) {
    value_ += n;
    return *this;
  }

  friend self_type operator+(const self_type& obj, difference_type n) {
    return self_type(obj.value_ + n);
  }

  friend difference_type operator-(const self_type& lhs, const self_type& rhs) {
    return lhs.value_ - rhs.value_;
  }

  value_type operator[](difference_type n) {
    return value_type(value_ + n);
  }

  friend bool operator<(const self_type& lhs, const self_type& rhs) {
    return lhs.value_ < rhs.value_;
  }

  friend bool operator==(const self_type& lhs, const self_type& rhs) {
    return lhs.value_ == rhs.value_;
  }

private:
  Integral value_;
};

/**
 * Helper function for building counting_iterator.
 *
 * Example:
 * <pre>
 * std::vector<int> v(make_counting_iterator(0), make_counting_iterator(5));
 * </pre>
 *
 * Produces v with elements {0, 1, 2, 3, 4}
 */
template <typename Integral>
auto make_counting_iterator(Integral n) -> counting_iterator<Integral> {
  return counting_iterator<Integral>(n);
}

/**
 * Random access iterator for iterating over integral type in reversed order.
 *
 * Example:
 * <pre>
 * std::vector<int> v(reverse_counting_iterator<int>(4), reverse_counting_iterator<int>(-1));
 * </pre>
 *
 * Produces v with elements {4, 3, 2, 1, 0}
 */
template <typename Integral>
class reverse_counting_iterator {
public:
  static_assert(std::is_integral<Integral>::value, "reverse_counting_iterator's template argument should be integral");
  using self_type = reverse_counting_iterator;
  using value_type = Integral;
  using reference = const value_type&;
  using pointer = const value_type*;
  using difference_type = typename std::make_signed<Integral>::type;
  using iterator_category = std::random_access_iterator_tag;

  reverse_counting_iterator(): value_() { }

  explicit reverse_counting_iterator(Integral n): value_(n) { }

  reference operator*() const {
    return value_;
  }

  self_type& operator++() {
    --value_;
    return *this;
  }

  self_type& operator--() {
    ++value_;
    return *this;
  }

  self_type& operator+=(difference_type n) {
    value_ -= n;
    return *this;
  }

  friend self_type operator+(const self_type& obj, difference_type n) {
    return self_type(obj.value_ - n);
  }

  friend difference_type operator-(const self_type& lhs, const self_type& rhs) {
    return rhs.value_ - lhs.value_;
  }

  value_type operator[](difference_type n) {
    return value_type(value_ - n);
  }

  friend bool operator<(const self_type& lhs, const self_type& rhs) {
    return rhs.value_ < lhs.value_;
  }

  friend bool operator==(const self_type& lhs, const self_type& rhs) {
    return lhs.value_ == rhs.value_;
  }

private:
  Integral value_;
};

/**
 * Helper function for building reverse_counting_iterator.
 *
 * Example:
 * <pre>
 * std::vector<int> v(make_reverse_counting_iterator(4), make_reverse_counting_iterator(-1));
 * </pre>
 *
 * Produces v with elements {4, 3, 2, 1, 0}
 */
template <typename Integral>
auto make_reverse_counting_iterator(Integral n) -> reverse_counting_iterator<Integral> {
  return reverse_counting_iterator<Integral>(n);
}

/**
 * Helper class for encapsulating iterator pair as iterable.
 *
 * Example:
 * <pre>
 * void foo(Iterator begin, Iterator end) {
 *    for (const auto& elem: iterator_range<Iterator>(begin, end)) {
 *      ...
 *    }
 * }
 * </pre>
 */
template <typename Iterator>
class iterator_range {
public:
  using iterator_type = Iterator;
  using reference = const Iterator&;

  static_assert(is_iterator<Iterator>::value, "iterator_range's template argument should be iterator!");

  explicit iterator_range(Iterator begin, Iterator end):
      begin_(std::move(begin)), end_(std::move(end)) { }

  reference begin() const {
    return begin_;
  }

  reference end() const {
    return end_;
  }

private:
  iterator_type begin_;
  iterator_type end_;
};

/**
 * Helper function for encapsulating iterator pair as iterable.
 *
 * Example:
 * <pre>
 * void foo(Iterator begin, Iterator end) {
 *    for (const auto& elem: make_range(begin, end)) {
 *      ...
 *    }
 * }
 * </pre>
 */
template <typename Iterator>
auto make_range(Iterator begin, Iterator end) -> iterator_range<Iterator> {
  return iterator_range<Iterator>(std::move(begin), std::move(end));
}

/**
 * Python-like range function.
 *
 * Example:
 * <pre>
 * for (auto i: range(0, 5)) {
 *    std::cout << i << ' ';
 * }
 * </pre>
 * Prints: 0 1 2 3 4
 *
 * You can also explicitly specify the type:
 * <pre>
 * for (auto i: range<uint32>(0, 5)) {
 *    std::cout << i << ' ';
 * }
 * </pre>
 */
template <typename Integral>
auto range(Integral begin, Integral end) ->
typename std::enable_if<std::is_integral<Integral>::value, iterator_range<counting_iterator<Integral>>>::type {
  return make_range(make_counting_iterator(begin), make_counting_iterator(end));
}

/**
 * Python-like function for iterating over reversed range.
 *
 * Example:
 * <pre>
 * for (auto i: rrange(0, 5)) {
 *    std::cout << i << ' ';
 * }
 * </pre>
 * Prints: 4 3 2 1 0
 *
 * You can also explicitly specify the type:
 * <pre>
 * for (auto i: rrange<uint32>(0, 5)) {
 *    std::cout << i << ' ';
 * }
 * </pre>
 */
template <typename Integral>
auto rrange(Integral begin, Integral end) ->
typename std::enable_if<std::is_integral<Integral>::value, iterator_range<reverse_counting_iterator<Integral>>>::type {
  return make_range(make_reverse_counting_iterator(end - 1), make_reverse_counting_iterator(begin - 1));
}

/**
 * Iterator performing transformation on values.
 *
 * Example:
 * <pre>
 * std::vector<int> v = {1, 2, 3};
 * using iterator = std::vector<int>::iterator;
 * using mapping_it = mapping_iterator<iterator, std::function<int(int)>>;
 * mapping_it it(v.begin(), [](int n) { return 2*n; });
 * mapping_it end(v.end());
 *
 * for (const auto& elem: make_range(it, end)) {
 *   std::cout << elem << ' ';
 * }
 * </pre>
 * Prints 2 4 6
 */
template <typename Iterator, typename Mapper>
class mapping_iterator {
public:
  using self_type = mapping_iterator;
  using underlying_value_type = decltype(*std::declval<Iterator>());
  using value_type = decltype(std::declval<Mapper>()(std::declval<underlying_value_type>()));
  using reference = value_type;
  using pointer = typename std::remove_reference<value_type>::type*;
  using difference_type = typename std::iterator_traits<Iterator>::difference_type;
  using iterator_category = typename std::iterator_traits<Iterator>::iterator_category;

  mapping_iterator(const Mapper& mapper = Mapper()):
      iterator_(), mapper_(mapper) { }

  explicit mapping_iterator(Iterator iterator, const Mapper& mapper = Mapper()):
      iterator_(iterator), mapper_(mapper) { }

  reference operator*() const {
    return mapper_(*iterator_);
  }

  self_type& operator++() {
    ++iterator_;
    return *this;
  }

  self_type& operator--() {
    --iterator_;
    return *this;
  }

  self_type& operator+=(difference_type n) {
    iterator_ += n;
    return *this;
  }

  friend self_type operator+(const self_type& obj, difference_type n) {
    return self_type(obj.iterator_ + n, obj.mapper_);
  }

  friend difference_type operator-(const self_type& lhs, const self_type& rhs) {
    return lhs.iterator_ - rhs.iterator_;
  }

  value_type operator[](difference_type n) {
    return *(*this + n);
  }

  friend bool operator<(const self_type& lhs, const self_type& rhs) {
    return lhs.iterator_ < rhs.iterator_;
  }

  friend bool operator==(const self_type& lhs, const self_type& rhs) {
    return lhs.iterator_ == rhs.iterator_;
  }

private:
  Iterator iterator_;
  Mapper mapper_;
};

namespace detail {

template <typename ValuesIterator>
struct IndirectMapper {
  static_assert(is_iterator<ValuesIterator>::value, "first indirect_iterator's template argument must be iterator.");
  static_assert(
      std::is_same<typename std::iterator_traits<ValuesIterator>::iterator_category, std::random_access_iterator_tag>::value,
      "ValuesIterator must be random assess iterator."
  );

  using value_type = typename std::iterator_traits<ValuesIterator>::value_type;
  using reference = const value_type&;
  using index_type = typename std::iterator_traits<ValuesIterator>::difference_type;

  IndirectMapper() = default;

  IndirectMapper(ValuesIterator values):
      values_(values) { }

  reference operator()(index_type n) const {
    return *(values_ + n);
  }

private:
  ValuesIterator values_;
};

} // namespace detail

template <typename ValuesIterator, typename IndexesIterator>
using indirect_iterator = mapping_iterator<IndexesIterator, detail::IndirectMapper<ValuesIterator>>;

/**
 * Iterates over random acess iterator with usage of permutation.
 *
 * Example:
 * <pre>
 * std::vector<int> perm = {2, 0, 1};
 * std::vector<std::string> values = {"Ala", "ma", "kota"};
 * auto it = make_indirect_iterator(values.begin(), perm.begin());
 * auto end = make_indirect_iterator(values.begin(), perm.end());
 * for (const auto& elem: make_range(it, end)) {
 *    std::cout << elem << ' ';
 * }
 * </pre>
 * Prints: kota Ala ma
 */
template <typename ValuesIterator, typename IndexesIterator>
auto make_indirect_iterator(ValuesIterator values, IndexesIterator indexes) ->
indirect_iterator<ValuesIterator, IndexesIterator> {
  detail::IndirectMapper<ValuesIterator> mapper(values);
  return indirect_iterator<ValuesIterator, IndexesIterator>(std::move(indexes), std::move(mapper));
};

/**
 * Base class for generators implementation.
 *
 * Example:
 * <pre>
 * for (auto gen = new foo_generator(); gen->hasNext(); ) {
 *    auto value = gen->next();
 *    ...
 * }
 * </pre>
 */
template <typename ValueType>
class generator {
public:
  using ptr = std::shared_ptr<generator>;
  using value_type = ValueType;

  generator() = default;
  generator(const generator&) = delete;
  generator& operator=(const generator&) = delete;
  generator(generator&&) = default;
  virtual ~generator() = default;

  /**
   * Generates new value and returns it.
   *
   * If there is no next value behaviour is undefined.
   */
  virtual value_type next() = 0;

  /**
   * Returns true if generator can generate new value.
   */
  virtual bool hasNext() = 0;
};

/**
 * Iterator for iterating over values returned by generator.
 *
 * Example:
 * <pre>
 * std::vector<uint32> v(generator_iterator<uint32>(new foo_generator()), generator_iterator<uint32>());
 * </pre>
 */
template <typename ValueType>
class generator_iterator {
public:
  using self_type = generator_iterator;
  using generator_type = generator<ValueType>;
  using generator_pointer = typename generator<ValueType>::ptr;
  using value_type = typename generator_type::value_type;
  using reference = const value_type&;
  using pointer = const value_type*;
  using difference_type = std::ptrdiff_t;
  using iterator_category = std::input_iterator_tag;

  generator_iterator() = default;

  generator_iterator(generator_type* generator):
      generator_iterator(generator_pointer(generator)) { }

  generator_iterator(generator_pointer generator):
      generator_(std::move(generator)) {
    advance();
  }

  reference operator*() const {
    return value_;
  }

  pointer operator->() const {
    return &value_;
  }

  self_type& operator++() {
    advance();
    return *this;
  }

  friend bool operator==(const self_type& lhs, const self_type& rhs) {
    return (&lhs == &rhs) || (lhs.is_end() && rhs.is_end());
  }

  bool is_end() const {
    return !bool(generator_.get());
  }

private:
  void advance() {
    if (generator_->hasNext())
      value_ = generator_->next();
    else
      generator_.reset();
  }

  generator_pointer generator_;
  value_type value_;
};

/**
 * Returns iterator range to values generated by generator.
 *
 * Example:
 * <pre>
 * for (const auto& elem: iterate_generator(new foo_generator())) {
 *    ...
 * }
 * </pre>
 */
template <typename T>
iterator_range<generator_iterator<T>> iterate_generator(generator<T>* gen) {
  return make_range(generator_iterator<T>(gen), generator_iterator<T>());
}

} // namespace lib
// Jakub Staroń, 2016

// Jakub Staroń, 2016


namespace lib {

namespace detail {

const int kSimpleFancyFlagID = std::ios_base::xalloc();

enum printing_type {
  simple_printing_type = 0,
  fancy_printing_type = 1
};

class delimiter_printer {
public:
  delimiter_printer(std::ostream& stream): first_(true) {
    fancy_ = (stream.iword(kSimpleFancyFlagID) == fancy_printing_type);
  }

  const char* prefix() {
    return fancy_? "(" : "";
  }

  const char* delimiter() {
    if (!first_) {
      return fancy_? ", " : " ";
    }
    else {
      first_ = false;
      return "";
    }
  }

  const char* postfix() {
    return fancy_? ")" : "";
  }

private:
  bool first_;
  bool fancy_;
};

template <typename T>
constexpr bool allow_print_operator() {
  return
      is_iterable<T>::value &&
      !std::is_same<T, std::string>::value &&
      !std::is_same<T, const char*>::value &&
      !std::is_same<typename std::remove_extent<T>::type, char>::value;
}

} // namespace detail

/**
 * Sets stream printing mode to simple. Default option.
 *
 * Example:
 * std::cout << simple << std::make_pair(1, 2) << std::endl;
 * Prints:
 * 1 2
 */
std::ostream& simple(std::ostream& stream) {
  stream.iword(detail::kSimpleFancyFlagID) = detail::simple_printing_type;
  return stream;
}

/**
 * Sets stream printing mode to fancy. Helpful for printing debug messages.
 *
 * Example:
 * std::cout << simple << std::make_pair(1, 2) << std::endl;
 * Prints:
 * (1, 2)
 */
std::ostream& fancy(std::ostream& stream) {
  stream.iword(detail::kSimpleFancyFlagID) = detail::fancy_printing_type;
  return stream;
}

/**
 * Overload operator<< for ostream and pair.
 */
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& stream, const std::pair<T1, T2>& pair);

/**
 * Overload operator<< for ostream and tuple.
 */
template <typename... Args>
std::ostream& operator<<(std::ostream& stream, const std::tuple<Args...>& tuple);

/**
 * Overload operator<< for ostream and every iterable (eg vector, map, array).
 */
template <typename Iterable>
typename std::enable_if<detail::allow_print_operator<Iterable>(), std::ostream&>::type
operator<<(std::ostream& stream, const Iterable& iterable);

#ifdef USE_INT128_TYPES

/**
 * Overload operator<< for ostream and uint128.
 */
std::ostream& operator<<(std::ostream& stream, uint128 n) {
  constexpr int32 buffer_size = 64;
  constexpr uint128 ten = 10;
  char buffer[buffer_size];
  int32 index = buffer_size - 1;

  do {
    uint128 digit = n % 10;
    buffer[index--] = char('0' + digit);
    n /= 10;
  } while (n > 0 && index >= 0);

  stream.write(buffer + index + 1, buffer_size - index - 1);
  return stream;
}

/**
 * Overload operator<< for ostream and int128.
 */
std::ostream& operator<<(std::ostream& stream, int128 n) {
  if (n < 0) {
    stream.put('-');
    n = -n;
  }
  stream << uint128(n);
  return stream;
}

#endif

/**
 * Overload operator<< for istream and pair.
 */
template <typename T1, typename T2>
std::istream& operator>>(std::istream& stream, std::pair<T1, T2>& pair);

/**
 * Overload operator<< for istream and tuple.
 */
template <typename... Args>
std::istream& operator>>(std::istream& stream, std::tuple<Args...>& tuple);

/**
 * Helper for marking input as ignored.
 *
 * Example:
 * int a, b;
 * std::cin >> a >> ignore<int>() >> b;
 */
template <typename T>
struct ignore {
  ignore() = default;

  friend std::istream& operator>>(std::istream& stream, const ignore&&) {
    T ignored;
    return stream >> ignored;
  }

  friend std::istream& operator>>(std::istream& stream, const ignore&) {
    T ignored;
    return stream >> ignored;
  }
};

namespace detail {

template<std::size_t...>
struct integer_sequence{};

template <size_t N>
struct generate_sequence {
private:
  template<std::size_t M, std::size_t... Is>
  struct helper {
    using type = typename helper<M-1, M-1, Is...>::type;
  };;

  template<std::size_t... Is>
  struct helper<0, Is...> {
    using type = integer_sequence<Is...>;
  };

public:
  using type = typename helper<N>::type;
};

template <typename Functor, size_t N>
struct dynamize {
  using functor_type = Functor;
private:
  using index_sequence = typename generate_sequence<N>::type;
  using function_type = void(functor_type::*)();
  using table_type = std::array<function_type, N>;

  template <size_t... Indexes>
  static constexpr table_type build_table(integer_sequence<Indexes...>) {
    return {{&functor_type::template operator()<Indexes>...}};
  }

  static constexpr table_type functions_ = build_table(index_sequence());
public:
  dynamize(functor_type&& functor):
      functor_(std::move(functor)) { }

  void call(size_t i) {
    if (i >= N)
      throw std::out_of_range("tuple_printer: out of range");

    (functor_.*functions_[i])();
  }

private:
  functor_type functor_;
};

template <typename Functor, size_t N>
constexpr typename dynamize<Functor, N>::table_type dynamize<Functor, N>::functions_;

template <typename... Args>
class tuple_printer {
  static constexpr size_t arguments_count = sizeof...(Args);
  using tuple_type = std::tuple<Args...>;

  struct impl {
    std::ostream& stream_;
    const tuple_type& tuple_;

    template <size_t N>
    void operator()() {
      stream_ << std::get<N>(tuple_);
    }
  };

public:
  tuple_printer (std::ostream& stream, const tuple_type& tuple):
    dynamize_(impl{stream, tuple}) { }

  void print(size_t i) {
    dynamize_.call(i);
  }

private:
  dynamize<impl, arguments_count> dynamize_;
};

template <typename... Args>
class tuple_reader {
  static constexpr size_t arguments_count = sizeof...(Args);
  using tuple_type = std::tuple<Args...>;

  struct impl {
    std::istream& stream_;
    tuple_type& tuple_;

    template <size_t N>
    void operator()() {
      stream_ >> std::get<N>(tuple_);
    }
  };

public:
  tuple_reader (std::istream& stream, tuple_type& tuple):
      dynamize_(impl{stream, tuple}) { }

  void read(size_t i) {
    dynamize_.call(i);
  }

private:
  dynamize<impl, arguments_count> dynamize_;
};

} // namespace detail

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& stream, const std::pair<T1, T2>& pair) {
  detail::delimiter_printer printer(stream);
  stream << printer.prefix();
  stream << printer.delimiter() << pair.first;
  stream << printer.delimiter() << pair.second;
  stream << printer.postfix();
  return stream;
}

template <typename... Args>
std::ostream& operator<<(std::ostream& stream, const std::tuple<Args...>& tuple) {
  detail::delimiter_printer delimiter_printer(stream);
  detail::tuple_printer<Args...> tuple_printer(stream, tuple);
  stream << delimiter_printer.prefix();
  for (auto i: range<size_t>(0, sizeof...(Args))) {
    stream << delimiter_printer.delimiter();
    tuple_printer.print(i);
  }
  stream << delimiter_printer.postfix();
  return stream;
}

template <typename Iterable>
typename std::enable_if<detail::allow_print_operator<Iterable>(), std::ostream&>::type
operator<<(std::ostream& stream, const Iterable& iterable) {
  detail::delimiter_printer printer(stream);
  stream << printer.prefix();
  for (const auto& elem: iterable) {
    stream << printer.delimiter() << elem;
  }
  stream << printer.postfix();
  return stream;
}

template <typename T1, typename T2>
std::istream& operator>>(std::istream& stream, std::pair<T1, T2>& pair) {
  return stream >> pair.first >> pair.second;
}

template <typename... Args>
std::istream& operator>>(std::istream& stream, std::tuple<Args...>& tuple) {
  detail::tuple_reader<Args...> tuple_reader(stream, tuple);
  for (auto i: range<size_t>(0, sizeof...(Args))) {
    tuple_reader.read(i);
  }
  return stream;
}


/**
 * Second version of overload operator>> for istream and pair.
 *
 * Needed to allow constructions like
 * int a, b, c;
 * std::cin >> std::tie(a, b, c);
 */
template <typename... Args>
std::istream& operator>>(std::istream& stream, std::tuple<Args...>&& tuple) {
  return stream >> tuple;
}

/**
 * Python-like print function.
 *
 * Example:
 * print(std::cerr, "1 + 2 = %0, 2 + 3 = %1", 3, 5);
 */
template <typename... Args>
void print(std::ostream& stream, const char* format, const Args&... args) {
  auto tuple = std::make_tuple(std::cref(args)...);
  detail::tuple_printer<const Args&...> tuple_printer(stream, tuple);
  constexpr char null = '\0';
  constexpr char percent = '%';
  for (const char* it = format, *prev = format; *it != '\0'; ) {
    while (*it != null && *it != percent)
      it++;

    stream.write(prev, it - prev);
    if (*it == percent) {
      ++it;
      if (*it == percent) {
        stream.put(percent);
      }
      else if (std::isdigit(*it)) {
        size_t index = size_t(*it - '0');
        tuple_printer.print(index);
      }
      else {
        throw std::invalid_argument("print - invalid character after %");
      }
      prev = ++it;
    }
  }
  stream.put('\n');
}

/**
 * Python-like print function. Prints to std::cout.
 */
template <typename... Args>
void print(const char* format, const Args&... args) {
  print(std::cout, format, args...);
}

/**
 * flush operator for usage with print.
 *
 * Example
 * print("important message%0", lib::flush);
 */
std::ostream& flush(std::ostream& stream) {
  return stream.flush();
}

/**
 * Python-like read function.
 *
 * Example:
 * int a, b;
 * read(std::cin, a, ignore<int>(), b);
 */
template <typename... Args>
void read(std::istream& stream, Args&&... args) {
  auto tuple = std::make_tuple(std::ref(args)...);
  stream >> tuple;
}

/**
 * Generator for reading lines from std::istream.
 */
class lines_generator: public generator<std::string> {
public:
  lines_generator(std::istream* stream):
      stream_(stream) { }

  value_type next() final {
    if (!stream_->good())
      throw std::ios::failure("lines_generator - stream in invalid state after line read.");
    else
      std::getline(*stream_, line_);
    return line_;
  }

  bool hasNext() final {
    return !stream_->eof();
  }

private:
  std::istream* stream_;
  std::string line_;
};

/**
 * Input iterator for reading lines from input.
 */
class lines_iterator: public generator_iterator<std::string> {
public:
  lines_iterator() = default;

  lines_iterator(std::istream* stream):
      generator_iterator(new lines_generator(stream)) { }
};

/**
 * Returns range of lines_iterator to iterate over all lines in stream.
 */
iterator_range<lines_iterator> iterate_lines(std::istream& stream) {
  return make_range(lines_iterator(&stream), lines_iterator());
}

} // namespace lib

namespace lib {
namespace logging {

enum class log_level {
  debug = 15,
  info = 10,
  error = 5,
  none = 0
};

class Logger {
public:
  friend Logger& get_logger(const std::string& name);

  Logger(Logger&& other):
      level_(other.level_),
      streams_(std::move(other.streams_)) { }

  Logger(const Logger&) = delete;
  Logger& operator=(const Logger&) = delete;

  template <typename... Args>
  void log(log_level level, const char* format, const Args&... args) {
    if (level > level_)
      return;

    for (const auto& pair: streams_) {
      if (level > pair.second)
        continue;

      print(*pair.first, format, args...);
    }
  }

  template <typename... Args>
  void debug(const char* format, const Args&... args) {
    log(log_level::debug, format, args...);
  }

  template <typename... Args>
  void info(const char* format, const Args&... args) {
    log(log_level::info, format, args...);
  }

  template <typename... Args>
  void error(const char* format, const Args&... args) {
    log(log_level::error, format, args...);
  }

  void add_stream(std::ostream* stream, log_level level) {
    streams_.emplace_back(stream, level);
  }

  void set_log_level(log_level level) {
    level_ = level;
  }

protected:
  Logger() = default;

private:
  log_level level_ = log_level::debug;
  std::vector<std::pair<std::ostream*, log_level>> streams_;
};

Logger& get_logger(const std::string& name) {
  static std::map<std::string, Logger> loggers;
  auto it = loggers.find(name);

  if (it == loggers.end()) {
    it = loggers.emplace(name, Logger()).first;
  }
  return it->second;
}

} // namespace logging
} // namespace lib

using namespace lib;

logging::Logger& logger = logging::get_logger("kar");

const char* const kWinning =   "WYGRANA";
const char* const kTying =     "REMIS";
const char* const kLoosing =   "PRZEGRANA";


class Application {
public:
  void Run() {
    std::vector<uint32> WinningWith(N, 0);
    std::vector<uint32> TyingWith(N, N);

    for (auto i: range<uint32>(0, M)) {
      uint32 a, b;
      char w;
      read(std::cin, a, w, b);
      a--, b--;

      logger.info("a = %0, w = %1, b = %2", a, w, b);

      if (w == '>') {
        TyingWith.at(b)--;
      }
      else if (w == '<') {
        WinningWith.at(b)++;
      }
      else {
        logger.error("Invalid type of edge: %0", w);
      }
    }

    auto Winning = std::count_if(WinningWith.begin(), WinningWith.end(),
                                 [](uint32 n) {
                                   return n > 0;
                                 });

    auto Tying = std::count_if(TyingWith.begin(), TyingWith.end(),
                                 [](uint32 n) {
                                   return n > 0;
                                 });

    if (Winning == N) {
      print(kLoosing); // Second player wins
    }
    else if (Tying == N) {
      print(kTying);
    }
    else {
      print(kWinning); // Second player can't defend himself
    }
  }

  void LoadData() {
    read(std::cin, N, M);
  }

private:
  uint32 N, M;
};

int main(int argc, const char* argv[]) {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  logger.set_log_level(logging::log_level::none);
  logger.add_stream(&std::cerr, logging::log_level::debug);
  uint32 T;
  read(std::cin, T);
  for (auto i: range<uint32>(0, T)) {
    logger.info("test no = %0", i);
    Application application;
    application.LoadData();
    application.Run();
  }
  return 0;
}

// Generated by include.py
// Jakub Staroń, 2016
// For more info see https://github.com/staronj/ProgrammingContestsLibrary
// Jakub Staroń, 2016

// Jakub Staroń, 2016

#include <iostream>
#include <sstream>
#include <iterator>
#include <type_traits>
#include <algorithm>
#include <memory>
#include <utility>
#include <functional>
#include <bitset>
#include <vector>
#include <array>
#include <list>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cinttypes>
#include <ctime>
#include <cctype>
#include <cstring>
#include <random>
#include <cassert>

namespace lib {

using int8    = std::int8_t;
using uint8   = std::uint8_t;
using int16   = std::int16_t;
using uint16  = std::uint16_t;
using int32   = std::int32_t;
using uint32  = std::uint32_t;
using int64   = std::int64_t;
using uint64  = std::uint64_t;

/**
 * Random number generator. Returns 32 bits numbers.
 *
 * You should prefer this random number generator over
 * C's rand(), because rand() max range is not strictly
 * defined and can be supringsly small (like 10000).
 */
std::knuth_b Random(time(0));

/**
 * 32 bits random generator.
 */
uint32 Random32() {
  return Random();
}

/**
 * 64 bits random generator.
 */
uint64 Random64() {
  return uint64(Random32()) << 32 | uint64(Random32());
}

#ifdef __SIZEOF_INT128__
#define HAVE_INT128_TYPES
#endif

#define USE_INT128_TYPES_IF_AVAILABLE 0

#if defined(HAVE_INT128_TYPES) && USE_INT128_TYPES_IF_AVAILABLE
#define USE_INT128_TYPES
#endif

#ifdef USE_INT128_TYPES
using int128 = __int128;
using uint128 = unsigned __int128;
#endif

using bit_vector = std::vector<bool>;

using char_pair     = std::pair<char, char>;
using bool_pair     = std::pair<bool, bool>;
using int32_pair    = std::pair<int32, int32>;
using uint32_pair   = std::pair<uint32, uint32>;
using int64_pair    = std::pair<int64, int64>;
using uint64_pair   = std::pair<uint64, uint64>;

} // namespace lib
// Jakub Staroń, 2016

// Jakub Staroń, 2016


namespace lib {

// post-incrementation -> pre-incrementation
template <typename T>
inline T operator++(T& obj, int) {
  T temp = obj;
  ++obj;
  return temp;
}

// post-decrementation -> pre-decrementation
template <typename T>
inline T operator--(T& obj, int) {
  T temp = obj;
  --obj;
  return temp;
}

// obj += n -> obj + n
template <typename T, typename Integral>
inline typename std::enable_if<std::is_integral<Integral>::value, T&>::type
operator+=(T& obj, Integral n) {
  obj = obj + n;
  return obj;
}

// obj1 += obj2 -> obj1 + obj2
template <typename T>
inline T& operator+=(T& obj1, const T& obj2) {
  obj1 = obj1 + obj2;
  return obj1;
}

// obj -= n -> obj - n
template <typename T, typename Integral>
inline typename std::enable_if<std::is_integral<Integral>::value, T&>::type
operator-=(T& obj, Integral n) {
  obj = obj - n;
  return obj;
}

// obj1 -= obj2 -> obj1 - obj2
template <typename T>
inline T& operator-=(T& obj1, const T& obj2) {
  obj1 = obj1 - obj2;
  return obj1;
}

// obj *= n -> obj * n
template <typename T, typename Integral>
inline typename std::enable_if<std::is_integral<Integral>::value, T&>::type
operator*=(T& obj, Integral n) {
  obj = obj * n;
  return obj;
}

// obj1 *= obj2 -> obj1 * obj2
template <typename T>
inline T& operator*=(T& obj1, const T& obj2) {
  obj1 = obj1 * obj2;
  return obj1;
}

// obj %= n -> obj % n
template <typename T, typename Integral>
inline typename std::enable_if<std::is_integral<Integral>::value, T&>::type
operator%=(T& obj, Integral n) {
  obj = obj % n;
  return obj;
}

// obj1 %= obj2 -> obj1 % obj2
template <typename T>
inline T& operator%=(T& obj1, const T& obj2) {
  obj1 = obj1 % obj2;
  return obj1;
}

// n + obj -> obj + n
template <typename T, typename Integral>
inline typename std::enable_if<std::is_integral<Integral>::value, T>::type
operator+(Integral n, const T& obj) {
  return obj + n;
}

// n * obj -> obj * n
template <typename T, typename Integral>
inline typename std::enable_if<std::is_integral<Integral>::value, T>::type
operator*(Integral n, const T& obj) {
  return obj * n;
}

// obj - n -> obj + (-n)
template <typename T, typename Integral>
inline typename std::enable_if<std::is_signed<Integral>::value, T>::type
operator-(const T& obj, Integral n) {
  return obj + (-n);
}

// obj -= n -> obj += (-n)
template <typename T, typename Integral>
inline typename std::enable_if<std::is_signed<Integral>::value, T&>::type
operator-=(const T& obj, Integral n) {
  return obj += (-n);
}

// lhs > rhs -> rhs < lhs
template <typename T>
inline bool operator>(const T& lhs, const T& rhs) {
  return rhs < lhs;
}

// lhs <= rhs -> !(rhs < lhs)
template <typename T>
inline bool operator<=(const T& lhs, const T& rhs) {
  return !(rhs < lhs);
}

// lhs >= rhs -> !(rhs < lhs)
template <typename T>
inline bool operator>=(const T& lhs, const T& rhs) {
  return rhs <= lhs;
}

// lhs >= rhs -> !(rhs < lhs)
template <typename T>
inline bool operator!=(const T& lhs, const T& rhs) {
  return !(lhs == rhs);
}

// + for pairs
template <typename Integral1, typename Integral2>
constexpr std::pair<Integral1, Integral2> operator+(const std::pair<Integral1, Integral2>& lhs, const std::pair<Integral1, Integral2>& rhs) {
  return std::pair<Integral1, Integral2>(lhs.first + rhs.first, lhs.second + rhs.second);
}

// - for pairs
template <typename Integral1, typename Integral2>
constexpr std::pair<Integral1, Integral2> operator-(const std::pair<Integral1, Integral2>& lhs, const std::pair<Integral1, Integral2>& rhs) {
  return std::pair<Integral1, Integral2>(lhs.first - rhs.first, lhs.second - rhs.second);
}

// % for pairs
template <typename Integral1, typename Integral2>
constexpr std::pair<Integral1, Integral2> operator%(const std::pair<Integral1, Integral2>& lhs, const std::pair<Integral1, Integral2>& rhs) {
  return std::pair<Integral1, Integral2>(lhs.first % rhs.first, lhs.second % rhs.second);
}

// * for pairs
template <typename Integral1, typename Integral2>
constexpr std::pair<Integral1, Integral2> operator*(const std::pair<Integral1, Integral2>& lhs, const std::pair<Integral1, Integral2>& rhs) {
  return std::pair<Integral1, Integral2>(lhs.first * rhs.first, lhs.second * rhs.second);
}

// % for (pair, Integral)
template <typename Integral1, typename Integral2, typename Integral3>
constexpr std::pair<Integral1, Integral2> operator%(const std::pair<Integral1, Integral2>& lhs, const Integral3& rhs) {
  return std::pair<Integral1, Integral2>(lhs.first % rhs, lhs.second % rhs);
}

// * for (pair, Integral)
template <typename Integral1, typename Integral2, typename Integral3>
constexpr std::pair<Integral1, Integral2> operator*(const std::pair<Integral1, Integral2>& lhs, const Integral3& rhs) {
  return std::pair<Integral1, Integral2>(lhs.first * rhs, lhs.second * rhs);
}


} // namespace lib

namespace lib {

/**
 * type_traits-like predicate. Equal to true_type if argument is iterator.
 *
 * Example:
 * <pre>
 * static_assert(is_iterator<std::vector<int>::iterator>::value, "vector iterator is not iterator! help!");
 * </pre>
 */
template<typename Iterator>
struct is_iterator {
private:
  template<typename I> static constexpr auto test(int)
  -> decltype(
      *std::declval<const I>(),
      std::declval<const I>() == std::declval<const I>(),
      std::declval<const I>() != std::declval<const I>(),
      ++ std::declval<I&>(),
      std::declval<I&>() ++,
      std::iterator_traits<I>(),
      bool()) { return
        std::is_destructible<I>::value;
  }

  template<typename I> static constexpr bool test(...) { return false; }

public:
  static constexpr bool value = test<Iterator>(0);
};

/**
 * type_traits-like predicate. Equal to true_type if argument is iteratorable.
 *
 * Example:
 * <pre>
 * static_assert(is_iteratorable<std::vector<int>>::value, "vector should be iterable!");
 * </pre>
 */
template<typename T>
struct is_iterable {
  template <typename C>
  using begin_t = decltype(std::begin(std::declval<C&>()));

  template <typename C>
  using end_t = decltype(std::end(std::declval<C&>()));

  template<typename I> static constexpr auto test(int)
  -> decltype(
      std::declval<begin_t<I>>(),
      std::declval<end_t<I>>(),
      bool()) { return
        std::is_same<begin_t<I>, end_t<I>>::value &&
        is_iterator<begin_t<I>>::value;
  }

  template<typename I> static constexpr bool test(...) { return false; }

public:
  static constexpr bool value = test<T>(0);
};

/**
 * Random access iterator for iterating over integral type.
 *
 * Example:
 * <pre>
 * std::vector<int> v(counting_iterator<int>(0), counting_iterator<int>(5));
 * </pre>
 *
 * Produces v with elements {0, 1, 2, 3, 4}
 */
template <typename Integral>
class counting_iterator {
public:
  static_assert(std::is_integral<Integral>::value, "counting_iterator's template argument should be integral");
  using self_type = counting_iterator;
  using value_type = Integral;
  using reference = const value_type&;
  using pointer = const value_type*;
  using difference_type = typename std::make_signed<Integral>::type;
  using iterator_category = std::random_access_iterator_tag;

  counting_iterator(): value_() { }

  explicit counting_iterator(Integral n): value_(n) { }

  reference operator*() const {
    return value_;
  }

  self_type& operator++() {
    ++value_;
    return *this;
  }

  self_type& operator--() {
    --value_;
    return *this;
  }

  self_type& operator+=(difference_type n) {
    value_ += n;
    return *this;
  }

  friend self_type operator+(const self_type& obj, difference_type n) {
    return self_type(obj.value_ + n);
  }

  friend difference_type operator-(const self_type& lhs, const self_type& rhs) {
    return lhs.value_ - rhs.value_;
  }

  value_type operator[](difference_type n) {
    return value_type(value_ + n);
  }

  friend bool operator<(const self_type& lhs, const self_type& rhs) {
    return lhs.value_ < rhs.value_;
  }

  friend bool operator==(const self_type& lhs, const self_type& rhs) {
    return lhs.value_ == rhs.value_;
  }

private:
  Integral value_;
};

/**
 * Helper function for building counting_iterator.
 *
 * Example:
 * <pre>
 * std::vector<int> v(make_counting_iterator(0), make_counting_iterator(5));
 * </pre>
 *
 * Produces v with elements {0, 1, 2, 3, 4}
 */
template <typename Integral>
auto make_counting_iterator(Integral n) -> counting_iterator<Integral> {
  return counting_iterator<Integral>(n);
}

/**
 * Random access iterator for iterating over integral type in reversed order.
 *
 * Example:
 * <pre>
 * std::vector<int> v(reverse_counting_iterator<int>(4), reverse_counting_iterator<int>(-1));
 * </pre>
 *
 * Produces v with elements {4, 3, 2, 1, 0}
 */
template <typename Integral>
class reverse_counting_iterator {
public:
  static_assert(std::is_integral<Integral>::value, "reverse_counting_iterator's template argument should be integral");
  using self_type = reverse_counting_iterator;
  using value_type = Integral;
  using reference = const value_type&;
  using pointer = const value_type*;
  using difference_type = typename std::make_signed<Integral>::type;
  using iterator_category = std::random_access_iterator_tag;

  reverse_counting_iterator(): value_() { }

  explicit reverse_counting_iterator(Integral n): value_(n) { }

  reference operator*() const {
    return value_;
  }

  self_type& operator++() {
    --value_;
    return *this;
  }

  self_type& operator--() {
    ++value_;
    return *this;
  }

  self_type& operator+=(difference_type n) {
    value_ -= n;
    return *this;
  }

  friend self_type operator+(const self_type& obj, difference_type n) {
    return self_type(obj.value_ - n);
  }

  friend difference_type operator-(const self_type& lhs, const self_type& rhs) {
    return rhs.value_ - lhs.value_;
  }

  value_type operator[](difference_type n) {
    return value_type(value_ - n);
  }

  friend bool operator<(const self_type& lhs, const self_type& rhs) {
    return rhs.value_ < lhs.value_;
  }

  friend bool operator==(const self_type& lhs, const self_type& rhs) {
    return lhs.value_ == rhs.value_;
  }

private:
  Integral value_;
};

/**
 * Helper function for building reverse_counting_iterator.
 *
 * Example:
 * <pre>
 * std::vector<int> v(make_reverse_counting_iterator(4), make_reverse_counting_iterator(-1));
 * </pre>
 *
 * Produces v with elements {4, 3, 2, 1, 0}
 */
template <typename Integral>
auto make_reverse_counting_iterator(Integral n) -> reverse_counting_iterator<Integral> {
  return reverse_counting_iterator<Integral>(n);
}

/**
 * Helper class for encapsulating iterator pair as iterable.
 *
 * Example:
 * <pre>
 * void foo(Iterator begin, Iterator end) {
 *    for (const auto& elem: iterator_range<Iterator>(begin, end)) {
 *      ...
 *    }
 * }
 * </pre>
 */
template <typename Iterator>
class iterator_range {
public:
  using iterator_type = Iterator;
  using reference = const Iterator&;

  static_assert(is_iterator<Iterator>::value, "iterator_range's template argument should be iterator!");

  explicit iterator_range(Iterator begin, Iterator end):
      begin_(std::move(begin)), end_(std::move(end)) { }

  reference begin() const {
    return begin_;
  }

  reference end() const {
    return end_;
  }

private:
  iterator_type begin_;
  iterator_type end_;
};

/**
 * Helper function for encapsulating iterator pair as iterable.
 *
 * Example:
 * <pre>
 * void foo(Iterator begin, Iterator end) {
 *    for (const auto& elem: make_range(begin, end)) {
 *      ...
 *    }
 * }
 * </pre>
 */
template <typename Iterator>
auto make_range(Iterator begin, Iterator end) -> iterator_range<Iterator> {
  return iterator_range<Iterator>(std::move(begin), std::move(end));
}

/**
 * Python-like range function.
 *
 * Example:
 * <pre>
 * for (auto i: range(0, 5)) {
 *    std::cout << i << ' ';
 * }
 * </pre>
 * Prints: 0 1 2 3 4
 *
 * You can also explicitly specify the type:
 * <pre>
 * for (auto i: range<uint32>(0, 5)) {
 *    std::cout << i << ' ';
 * }
 * </pre>
 */
template <typename Integral>
auto range(Integral begin, Integral end) ->
typename std::enable_if<std::is_integral<Integral>::value, iterator_range<counting_iterator<Integral>>>::type {
  return make_range(make_counting_iterator(begin), make_counting_iterator(end));
}

/**
 * Python-like function for iterating over reversed range.
 *
 * Example:
 * <pre>
 * for (auto i: rrange(0, 5)) {
 *    std::cout << i << ' ';
 * }
 * </pre>
 * Prints: 4 3 2 1 0
 *
 * You can also explicitly specify the type:
 * <pre>
 * for (auto i: rrange<uint32>(0, 5)) {
 *    std::cout << i << ' ';
 * }
 * </pre>
 */
template <typename Integral>
auto rrange(Integral begin, Integral end) ->
typename std::enable_if<std::is_integral<Integral>::value, iterator_range<reverse_counting_iterator<Integral>>>::type {
  return make_range(make_reverse_counting_iterator(end - 1), make_reverse_counting_iterator(begin - 1));
}

/**
 * Iterator performing transformation on values.
 *
 * Example:
 * <pre>
 * std::vector<int> v = {1, 2, 3};
 * using iterator = std::vector<int>::iterator;
 * using mapping_it = mapping_iterator<iterator, std::function<int(int)>>;
 * mapping_it it(v.begin(), [](int n) { return 2*n; });
 * mapping_it end(v.end());
 *
 * for (const auto& elem: make_range(it, end)) {
 *   std::cout << elem << ' ';
 * }
 * </pre>
 * Prints 2 4 6
 */
template <typename Iterator, typename Mapper>
class mapping_iterator {
public:
  using self_type = mapping_iterator;
  using underlying_value_type = decltype(*std::declval<Iterator>());
  using value_type = decltype(std::declval<Mapper>()(std::declval<underlying_value_type>()));
  using reference = value_type;
  using pointer = typename std::remove_reference<value_type>::type*;
  using difference_type = typename std::iterator_traits<Iterator>::difference_type;
  using iterator_category = typename std::iterator_traits<Iterator>::iterator_category;

  mapping_iterator(const Mapper& mapper = Mapper()):
      iterator_(), mapper_(mapper) { }

  explicit mapping_iterator(Iterator iterator, const Mapper& mapper = Mapper()):
      iterator_(iterator), mapper_(mapper) { }

  reference operator*() const {
    return mapper_(*iterator_);
  }

  self_type& operator++() {
    ++iterator_;
    return *this;
  }

  self_type& operator--() {
    --iterator_;
    return *this;
  }

  self_type& operator+=(difference_type n) {
    iterator_ += n;
    return *this;
  }

  friend self_type operator+(const self_type& obj, difference_type n) {
    return self_type(obj.iterator_ + n, obj.mapper_);
  }

  friend difference_type operator-(const self_type& lhs, const self_type& rhs) {
    return lhs.iterator_ - rhs.iterator_;
  }

  value_type operator[](difference_type n) {
    return *(*this + n);
  }

  friend bool operator<(const self_type& lhs, const self_type& rhs) {
    return lhs.iterator_ < rhs.iterator_;
  }

  friend bool operator==(const self_type& lhs, const self_type& rhs) {
    return lhs.iterator_ == rhs.iterator_;
  }

private:
  Iterator iterator_;
  Mapper mapper_;
};

namespace detail {

template <typename ValuesIterator>
struct IndirectMapper {
  static_assert(is_iterator<ValuesIterator>::value, "first indirect_iterator's template argument must be iterator.");
  static_assert(
      std::is_same<typename std::iterator_traits<ValuesIterator>::iterator_category, std::random_access_iterator_tag>::value,
      "ValuesIterator must be random assess iterator."
  );

  using value_type = typename std::iterator_traits<ValuesIterator>::value_type;
  using reference = const value_type&;
  using index_type = typename std::iterator_traits<ValuesIterator>::difference_type;

  IndirectMapper() = default;

  IndirectMapper(ValuesIterator values):
      values_(values) { }

  reference operator()(index_type n) const {
    return *(values_ + n);
  }

private:
  ValuesIterator values_;
};

} // namespace detail

template <typename ValuesIterator, typename IndexesIterator>
using indirect_iterator = mapping_iterator<IndexesIterator, detail::IndirectMapper<ValuesIterator>>;

/**
 * Iterates over random acess iterator with usage of permutation.
 *
 * Example:
 * <pre>
 * std::vector<int> perm = {2, 0, 1};
 * std::vector<std::string> values = {"Ala", "ma", "kota"};
 * auto it = make_indirect_iterator(values.begin(), perm.begin());
 * auto end = make_indirect_iterator(values.begin(), perm.end());
 * for (const auto& elem: make_range(it, end)) {
 *    std::cout << elem << ' ';
 * }
 * </pre>
 * Prints: kota Ala ma
 */
template <typename ValuesIterator, typename IndexesIterator>
auto make_indirect_iterator(ValuesIterator values, IndexesIterator indexes) ->
indirect_iterator<ValuesIterator, IndexesIterator> {
  detail::IndirectMapper<ValuesIterator> mapper(values);
  return indirect_iterator<ValuesIterator, IndexesIterator>(std::move(indexes), std::move(mapper));
};

/**
 * Base class for generators implementation.
 *
 * Example:
 * <pre>
 * for (auto gen = new foo_generator(); gen->hasNext(); ) {
 *    auto value = gen->next();
 *    ...
 * }
 * </pre>
 */
template <typename ValueType>
class generator {
public:
  using ptr = std::shared_ptr<generator>;
  using value_type = ValueType;

  generator() = default;
  generator(const generator&) = delete;
  generator& operator=(const generator&) = delete;
  generator(generator&&) = default;
  virtual ~generator() = default;

  /**
   * Generates new value and returns it.
   *
   * If there is no next value behaviour is undefined.
   */
  virtual value_type next() = 0;

  /**
   * Returns true if generator can generate new value.
   */
  virtual bool hasNext() = 0;
};

/**
 * Iterator for iterating over values returned by generator.
 *
 * Example:
 * <pre>
 * std::vector<uint32> v(generator_iterator<uint32>(new foo_generator()), generator_iterator<uint32>());
 * </pre>
 */
template <typename ValueType>
class generator_iterator {
public:
  using self_type = generator_iterator;
  using generator_type = generator<ValueType>;
  using generator_pointer = typename generator<ValueType>::ptr;
  using value_type = typename generator_type::value_type;
  using reference = const value_type&;
  using pointer = const value_type*;
  using difference_type = std::ptrdiff_t;
  using iterator_category = std::input_iterator_tag;

  generator_iterator() = default;

  generator_iterator(generator_type* generator):
      generator_iterator(generator_pointer(generator)) { }

  generator_iterator(generator_pointer generator):
      generator_(std::move(generator)) {
    advance();
  }

  reference operator*() const {
    return value_;
  }

  pointer operator->() const {
    return &value_;
  }

  self_type& operator++() {
    advance();
    return *this;
  }

  friend bool operator==(const self_type& lhs, const self_type& rhs) {
    return (&lhs == &rhs) || (lhs.is_end() && rhs.is_end());
  }

  bool is_end() const {
    return !bool(generator_.get());
  }

private:
  void advance() {
    if (generator_->hasNext())
      value_ = generator_->next();
    else
      generator_.reset();
  }

  generator_pointer generator_;
  value_type value_;
};

/**
 * Returns iterator range to values generated by generator.
 *
 * Example:
 * <pre>
 * for (const auto& elem: iterate_generator(new foo_generator())) {
 *    ...
 * }
 * </pre>
 */
template <typename T>
iterator_range<generator_iterator<T>> iterate_generator(generator<T>* gen) {
  return make_range(generator_iterator<T>(gen), generator_iterator<T>());
}

} // namespace lib
// Jakub Staroń, 2016

// Jakub Staroń, 2016


namespace lib {

namespace detail {

const int kSimpleFancyFlagID = std::ios_base::xalloc();

enum printing_type {
  simple_printing_type = 0,
  fancy_printing_type = 1
};

class delimiter_printer {
public:
  delimiter_printer(std::ostream& stream): first_(true) {
    fancy_ = (stream.iword(kSimpleFancyFlagID) == fancy_printing_type);
  }

  const char* prefix() {
    return fancy_? "(" : "";
  }

  const char* delimiter() {
    if (!first_) {
      return fancy_? ", " : " ";
    }
    else {
      first_ = false;
      return "";
    }
  }

  const char* postfix() {
    return fancy_? ")" : "";
  }

private:
  bool first_;
  bool fancy_;
};

template <typename T>
constexpr bool allow_print_operator() {
  return
      is_iterable<T>::value &&
      !std::is_same<T, std::string>::value &&
      !std::is_same<T, const char*>::value &&
      !std::is_same<typename std::remove_extent<T>::type, char>::value;
}

} // namespace detail

/**
 * Sets stream printing mode to simple. Default option.
 *
 * Example:
 * std::cout << simple << std::make_pair(1, 2) << std::endl;
 * Prints:
 * 1 2
 */
std::ostream& simple(std::ostream& stream) {
  stream.iword(detail::kSimpleFancyFlagID) = detail::simple_printing_type;
  return stream;
}

/**
 * Sets stream printing mode to fancy. Helpful for printing debug messages.
 *
 * Example:
 * std::cout << simple << std::make_pair(1, 2) << std::endl;
 * Prints:
 * (1, 2)
 */
std::ostream& fancy(std::ostream& stream) {
  stream.iword(detail::kSimpleFancyFlagID) = detail::fancy_printing_type;
  return stream;
}

/**
 * Overload operator<< for ostream and pair.
 */
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& stream, const std::pair<T1, T2>& pair);

/**
 * Overload operator<< for ostream and tuple.
 */
template <typename... Args>
std::ostream& operator<<(std::ostream& stream, const std::tuple<Args...>& tuple);

/**
 * Overload operator<< for ostream and every iterable (eg vector, map, array).
 */
template <typename Iterable>
typename std::enable_if<detail::allow_print_operator<Iterable>(), std::ostream&>::type
operator<<(std::ostream& stream, const Iterable& iterable);

#ifdef USE_INT128_TYPES

/**
 * Overload operator<< for ostream and uint128.
 */
std::ostream& operator<<(std::ostream& stream, uint128 n) {
  constexpr int32 buffer_size = 64;
  constexpr uint128 ten = 10;
  char buffer[buffer_size];
  int32 index = buffer_size - 1;

  do {
    uint128 digit = n % 10;
    buffer[index--] = char('0' + digit);
    n /= 10;
  } while (n > 0 && index >= 0);

  stream.write(buffer + index + 1, buffer_size - index - 1);
  return stream;
}

/**
 * Overload operator<< for ostream and int128.
 */
std::ostream& operator<<(std::ostream& stream, int128 n) {
  if (n < 0) {
    stream.put('-');
    n = -n;
  }
  stream << uint128(n);
  return stream;
}

#endif

/**
 * Overload operator<< for istream and pair.
 */
template <typename T1, typename T2>
std::istream& operator>>(std::istream& stream, std::pair<T1, T2>& pair);

/**
 * Overload operator<< for istream and tuple.
 */
template <typename... Args>
std::istream& operator>>(std::istream& stream, std::tuple<Args...>& tuple);

/**
 * Helper for marking input as ignored.
 *
 * Example:
 * int a, b;
 * std::cin >> a >> ignore<int>() >> b;
 */
template <typename T>
struct ignore {
  ignore() = default;

  friend std::istream& operator>>(std::istream& stream, const ignore&&) {
    T ignored;
    return stream >> ignored;
  }

  friend std::istream& operator>>(std::istream& stream, const ignore&) {
    T ignored;
    return stream >> ignored;
  }
};

namespace detail {

template<std::size_t...>
struct integer_sequence{};

template <size_t N>
struct generate_sequence {
private:
  template<std::size_t M, std::size_t... Is>
  struct helper {
    using type = typename helper<M-1, M-1, Is...>::type;
  };;

  template<std::size_t... Is>
  struct helper<0, Is...> {
    using type = integer_sequence<Is...>;
  };

public:
  using type = typename helper<N>::type;
};

template <typename Functor, size_t N>
struct dynamize {
  using functor_type = Functor;
private:
  using index_sequence = typename generate_sequence<N>::type;
  using function_type = void(functor_type::*)();
  using table_type = std::array<function_type, N>;

  template <size_t... Indexes>
  static constexpr table_type build_table(integer_sequence<Indexes...>) {
    return {{&functor_type::template operator()<Indexes>...}};
  }

  static constexpr table_type functions_ = build_table(index_sequence());
public:
  dynamize(functor_type&& functor):
      functor_(std::move(functor)) { }

  void call(size_t i) {
    if (i >= N)
      throw std::out_of_range("tuple_printer: out of range");

    (functor_.*functions_[i])();
  }

private:
  functor_type functor_;
};

template <typename Functor, size_t N>
constexpr typename dynamize<Functor, N>::table_type dynamize<Functor, N>::functions_;

template <typename... Args>
class tuple_printer {
  static constexpr size_t arguments_count = sizeof...(Args);
  using tuple_type = std::tuple<Args...>;

  struct impl {
    std::ostream& stream_;
    const tuple_type& tuple_;

    template <size_t N>
    void operator()() {
      stream_ << std::get<N>(tuple_);
    }
  };

public:
  tuple_printer (std::ostream& stream, const tuple_type& tuple):
    dynamize_(impl{stream, tuple}) { }

  void print(size_t i) {
    dynamize_.call(i);
  }

private:
  dynamize<impl, arguments_count> dynamize_;
};

template <typename... Args>
class tuple_reader {
  static constexpr size_t arguments_count = sizeof...(Args);
  using tuple_type = std::tuple<Args...>;

  struct impl {
    std::istream& stream_;
    tuple_type& tuple_;

    template <size_t N>
    void operator()() {
      stream_ >> std::get<N>(tuple_);
    }
  };

public:
  tuple_reader (std::istream& stream, tuple_type& tuple):
      dynamize_(impl{stream, tuple}) { }

  void read(size_t i) {
    dynamize_.call(i);
  }

private:
  dynamize<impl, arguments_count> dynamize_;
};

} // namespace detail

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& stream, const std::pair<T1, T2>& pair) {
  detail::delimiter_printer printer(stream);
  stream << printer.prefix();
  stream << printer.delimiter() << pair.first;
  stream << printer.delimiter() << pair.second;
  stream << printer.postfix();
  return stream;
}

template <typename... Args>
std::ostream& operator<<(std::ostream& stream, const std::tuple<Args...>& tuple) {
  detail::delimiter_printer delimiter_printer(stream);
  detail::tuple_printer<Args...> tuple_printer(stream, tuple);
  stream << delimiter_printer.prefix();
  for (auto i: range<size_t>(0, sizeof...(Args))) {
    stream << delimiter_printer.delimiter();
    tuple_printer.print(i);
  }
  stream << delimiter_printer.postfix();
  return stream;
}

template <typename Iterable>
typename std::enable_if<detail::allow_print_operator<Iterable>(), std::ostream&>::type
operator<<(std::ostream& stream, const Iterable& iterable) {
  detail::delimiter_printer printer(stream);
  stream << printer.prefix();
  for (const auto& elem: iterable) {
    stream << printer.delimiter() << elem;
  }
  stream << printer.postfix();
  return stream;
}

template <typename T1, typename T2>
std::istream& operator>>(std::istream& stream, std::pair<T1, T2>& pair) {
  return stream >> pair.first >> pair.second;
}

template <typename... Args>
std::istream& operator>>(std::istream& stream, std::tuple<Args...>& tuple) {
  detail::tuple_reader<Args...> tuple_reader(stream, tuple);
  for (auto i: range<size_t>(0, sizeof...(Args))) {
    tuple_reader.read(i);
  }
  return stream;
}


/**
 * Second version of overload operator>> for istream and pair.
 *
 * Needed to allow constructions like
 * int a, b, c;
 * std::cin >> std::tie(a, b, c);
 */
template <typename... Args>
std::istream& operator>>(std::istream& stream, std::tuple<Args...>&& tuple) {
  return stream >> tuple;
}

/**
 * Python-like print function.
 *
 * Example:
 * print(std::cerr, "1 + 2 = %0, 2 + 3 = %1", 3, 5);
 */
template <typename... Args>
void print(std::ostream& stream, const char* format, const Args&... args) {
  auto tuple = std::make_tuple(std::cref(args)...);
  detail::tuple_printer<const Args&...> tuple_printer(stream, tuple);
  constexpr char null = '\0';
  constexpr char percent = '%';
  for (const char* it = format, *prev = format; *it != '\0'; ) {
    while (*it != null && *it != percent)
      it++;

    stream.write(prev, it - prev);
    if (*it == percent) {
      ++it;
      if (*it == percent) {
        stream.put(percent);
      }
      else if (std::isdigit(*it)) {
        size_t index = size_t(*it - '0');
        tuple_printer.print(index);
      }
      else {
        throw std::invalid_argument("print - invalid character after %");
      }
      prev = ++it;
    }
  }
  stream.put('\n');
}

/**
 * Python-like print function. Prints to std::cout.
 */
template <typename... Args>
void print(const char* format, const Args&... args) {
  print(std::cout, format, args...);
}

/**
 * flush operator for usage with print.
 *
 * Example
 * print("important message%0", lib::flush);
 */
std::ostream& flush(std::ostream& stream) {
  return stream.flush();
}

/**
 * Python-like read function.
 *
 * Example:
 * int a, b;
 * read(std::cin, a, ignore<int>(), b);
 */
template <typename... Args>
void read(std::istream& stream, Args&&... args) {
  auto tuple = std::make_tuple(std::ref(args)...);
  stream >> tuple;
}

/**
 * Generator for reading lines from std::istream.
 */
class lines_generator: public generator<std::string> {
public:
  lines_generator(std::istream* stream):
      stream_(stream) { }

  value_type next() final {
    if (!stream_->good())
      throw std::ios::failure("lines_generator - stream in invalid state after line read.");
    else
      std::getline(*stream_, line_);
    return line_;
  }

  bool hasNext() final {
    return !stream_->eof();
  }

private:
  std::istream* stream_;
  std::string line_;
};

/**
 * Input iterator for reading lines from input.
 */
class lines_iterator: public generator_iterator<std::string> {
public:
  lines_iterator() = default;

  lines_iterator(std::istream* stream):
      generator_iterator(new lines_generator(stream)) { }
};

/**
 * Returns range of lines_iterator to iterate over all lines in stream.
 */
iterator_range<lines_iterator> iterate_lines(std::istream& stream) {
  return make_range(lines_iterator(&stream), lines_iterator());
}

} // namespace lib

namespace lib {
namespace logging {

enum class log_level {
  debug = 15,
  info = 10,
  error = 5,
  none = 0
};

class Logger {
public:
  friend Logger& get_logger(const std::string& name);

  Logger(Logger&& other):
      level_(other.level_),
      streams_(std::move(other.streams_)) { }

  Logger(const Logger&) = delete;
  Logger& operator=(const Logger&) = delete;

  template <typename... Args>
  void log(log_level level, const char* format, const Args&... args) {
    if (level > level_)
      return;

    for (const auto& pair: streams_) {
      if (level > pair.second)
        continue;

      print(*pair.first, format, args...);
    }
  }

  template <typename... Args>
  void debug(const char* format, const Args&... args) {
    log(log_level::debug, format, args...);
  }

  template <typename... Args>
  void info(const char* format, const Args&... args) {
    log(log_level::info, format, args...);
  }

  template <typename... Args>
  void error(const char* format, const Args&... args) {
    log(log_level::error, format, args...);
  }

  void add_stream(std::ostream* stream, log_level level) {
    streams_.emplace_back(stream, level);
  }

  void set_log_level(log_level level) {
    level_ = level;
  }

protected:
  Logger() = default;

private:
  log_level level_ = log_level::debug;
  std::vector<std::pair<std::ostream*, log_level>> streams_;
};

Logger& get_logger(const std::string& name) {
  static std::map<std::string, Logger> loggers;
  auto it = loggers.find(name);

  if (it == loggers.end()) {
    it = loggers.emplace(name, Logger()).first;
  }
  return it->second;
}

} // namespace logging
} // namespace lib

using namespace lib;

logging::Logger& logger = logging::get_logger("kar");

const char* const kWinning =   "WYGRANA";
const char* const kTying =     "REMIS";
const char* const kLoosing =   "PRZEGRANA";


class Application {
public:
  void Run() {
    std::vector<uint32> WinningWith(N, 0);
    std::vector<uint32> TyingWith(N, N);

    for (auto i: range<uint32>(0, M)) {
      uint32 a, b;
      char w;
      read(std::cin, a, w, b);
      a--, b--;

      logger.info("a = %0, w = %1, b = %2", a, w, b);

      if (w == '>') {
        TyingWith.at(b)--;
      }
      else if (w == '<') {
        WinningWith.at(b)++;
      }
      else {
        logger.error("Invalid type of edge: %0", w);
      }
    }

    auto Winning = std::count_if(WinningWith.begin(), WinningWith.end(),
                                 [](uint32 n) {
                                   return n > 0;
                                 });

    auto Tying = std::count_if(TyingWith.begin(), TyingWith.end(),
                                 [](uint32 n) {
                                   return n > 0;
                                 });

    if (Winning == N) {
      print(kLoosing); // Second player wins
    }
    else if (Tying == N) {
      print(kTying);
    }
    else {
      print(kWinning); // Second player can't defend himself
    }
  }

  void LoadData() {
    read(std::cin, N, M);
  }

private:
  uint32 N, M;
};

int main(int argc, const char* argv[]) {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  logger.set_log_level(logging::log_level::none);
  logger.add_stream(&std::cerr, logging::log_level::debug);
  uint32 T;
  read(std::cin, T);
  for (auto i: range<uint32>(0, T)) {
    logger.info("test no = %0", i);
    Application application;
    application.LoadData();
    application.Run();
  }
  return 0;
}