比赛记录 - Codeforces Round #831 (Div. 1 + Div. 2)

发表于 更新于 分类于 本文字数： 4.6k 阅读时长 ≈ 17 分钟

比赛链接

进度: 5 / 9

A - Factorise N+M

Pak Chanek has a prime number\(^\dagger\) \(n\). Find a prime number \(m\) such that \(n + m\) is not prime.

\(^\dagger\) A prime number is a number with exactly \(2\) factors. The first few prime numbers are \(2,3,5,7,11,13,\ldots\). In particular, \(1\) is not a prime number.

Input

Each test contains multiple test cases. The first line contains an integer \(t\) (\(1 \leq t \leq 10^4\)) — the number of test cases. The following lines contain the description of each test case.

The only line of each test case contains a prime number \(n\) (\(2 \leq n \leq 10^5\)).

Output

For each test case, output a line containing a prime number \(m\) (\(2 \leq m \leq 10^5\)) such that \(n + m\) is not prime. It can be proven that under the constraints of the problem, such \(m\) always exists.

If there are multiple solutions, you can output any of them.

Example

input

1
2
3
4
3
7
2
75619

output

1
2
3
2
7
47837

Note

In the first test case, \(m = 2\), which is prime, and \(n + m = 7 + 2 = 9\), which is not prime.

In the second test case, \(m = 7\), which is prime, and \(n + m = 2 + 7 = 9\), which is not prime.

In the third test case, \(m = 47837\), which is prime, and \(n + m = 75619 + 47837 = 123456\), which is not prime.

代码参考

Show code

CodeForces_1740Aview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
struct CustomHash {
  static constexpr uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static constexpr size_t append(size_t x, size_t y) {
    return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1));
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  template <class Tp, class Up>
  size_t operator()(std::pair<Tp, Up> const &p) const {
    return append((*this)(p.first), (*this)(p.second));
  }
  template <typename... Ts>
  size_t operator()(std::tuple<Ts...> const &tp) const {
    size_t ret = 0;
    std::apply(
      [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); },
      tp);
    return ret;
  }
  template <
    class Tp,
    std::enable_if_t<std::is_same_v<decltype(std::declval<Tp>().begin()),
                                    typename Tp::iterator> &&
                     std::is_same_v<decltype(std::declval<Tp>().end()),
                                    typename Tp::iterator>> * = nullptr>
  size_t operator()(Tp const &tp) const {
    size_t ret = 0;
    for (auto &&i : tp) ret = append(ret, (*this)(i));
    return ret;
  }
};
using i64 = int64_t;
#define read_var_(type, name) \
  type name;                  \
  std::cin >> name
template <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(Tp i) -> bool {
  return i && (i & -i) == i;
}
#define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple>>
namespace tuple_detail_ {
template <std::size_t Begin, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
apply2_impl_(BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) {
  return std::make_tuple(
    std::forward<BinOp>(f)(std::get<Is>(lhs), std::get<Is>(rhs))...);
}
}  // namespace tuple_detail_
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(Tuple &&t) {
  static_assert(Begin <= TPL_SIZE_(Tuple) && Len <= TPL_SIZE_(Tuple) &&
                  Begin + Len <= TPL_SIZE_(Tuple),
                "Out of range");
  return tuple_detail_::subtuple_impl_<Begin>(t,
                                              std::make_index_sequence<Len>());
}
template <std::size_t Pos, class Tp, class Tuple>
constexpr auto tuple_push(Tp &&v, Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        std::make_tuple(v),
                        subtuple<Pos, TPL_SIZE_(Tuple) - Pos>(t));
}
template <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_pop(Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        subtuple<Pos + 1, TPL_SIZE_(Tuple) - Pos - 1>(t));
}
template <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(BinOp &&f, Tuple &&lhs, Tuple &&rhs) {
  return tuple_detail_::apply2_impl_(
    f, lhs, rhs, std::make_index_sequence<TPL_SIZE_(Tuple)>());
}
#define OO_PTEQ_(op)                                                          \
  template <class Tp, class Up>                                               \
  constexpr auto operator op(std::pair<Tp, Up> lhs,                           \
                             const std::pair<Tp, Up> &rhs) {                  \
    return {lhs.first op rhs.first, lhs.second op rhs.second};                \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op(std::tuple<Ts...> const &lhs,                    \
                             std::tuple<Ts...> const &rhs) {                  \
    return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs);       \
  }                                                                           \
  template <class Tp, class Up>                                               \
  constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs,         \
                                              const std::pair<Tp, Up> &rhs) { \
    lhs.first op## = rhs.first;                                               \
    lhs.second op## = rhs.second;                                             \
    return lhs;                                                               \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op##=(std::tuple<Ts...> &lhs,                       \
                                const std::tuple<Ts...> &rhs) {               \
    return lhs = lhs op rhs;                                                  \
  }
OO_PTEQ_(+)
OO_PTEQ_(-)
OO_PTEQ_(*)
OO_PTEQ_(/)
OO_PTEQ_(%)
OO_PTEQ_(&)
OO_PTEQ_(|)
OO_PTEQ_(^)
OO_PTEQ_(<<)
OO_PTEQ_(>>)
#undef OO_PTEQ_
#undef TPL_SIZE_
template <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
std::ostream &operator<<(std::ostream &os, const std::pair<Tp, Up> &p) {
  return os << p.first << ' ' << p.second;
}
template <typename... Ts>
std::istream &operator>>(std::istream &is, std::tuple<Ts...> &p) {
  std::apply([&](Ts &...targs) { ((is >> targs), ...); }, p);
  return is;
}
template <typename... Ts>
std::ostream &operator<<(std::ostream &os, const std::tuple<Ts...> &p) {
  std::apply(
    [&](Ts const &...targs) {
      std::size_t n{0};
      ((os << targs << (++n != sizeof...(Ts) ? " " : "")), ...);
    },
    p);
  return os;
}
template <class Ch,
          class Tr,
          class Ct,
          std::enable_if_t<std::is_same_v<decltype(std::declval<Ct>().begin()),
                                          typename Ct::iterator> &&
                           std::is_same_v<decltype(std::declval<Ct>().end()),
                                          typename Ct::iterator>> * = nullptr>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os,
                                       const Ct &x) {
  if (x.begin() == x.end()) return os;
  for (auto it = x.begin(); it != x.end() - 1; ++it) os << *it << ' ';
  os << x.back();
  return os;
}
using namespace std;
auto solve([[maybe_unused]] int t_ = 0) -> void {
  read_var_(i64, n);
  cout << ((n & 1) ? 3 : 2) << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

B - Jumbo Extra Cheese 2

Pak Chanek has \(n\) two-dimensional slices of cheese. The \(i\)-th slice of cheese can be represented as a rectangle of dimensions \(a_i \times b_i\). We want to arrange them on the two-dimensional plane such that:

  • Each edge of each cheese is parallel to either the x-axis or the y-axis.
  • The bottom edge of each cheese is a segment of the x-axis.
  • No two slices of cheese overlap, but their sides can touch.
  • They form one connected shape.

Note that we can arrange them in any order (the leftmost slice of cheese is not necessarily the first slice of cheese). Also note that we can rotate each slice of cheese in any way as long as all conditions still hold.

Find the minimum possible perimeter of the constructed shape.

Input

Each test contains multiple test cases. The first line contains an integer \(t\) (\(1 \leq t \leq 2 \cdot 10^4\)) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) — the number of slices of cheese Pak Chanek has.

The \(i\)-th of the next \(n\) lines of each test case contains two integers \(a_i\) and \(b_i\) (\(1 \leq a_i,b_i \leq 10^9\)) — the dimensions of the \(i\)-th slice of cheese.

It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2 \cdot 10^5\).

Output

For each test case, output a line containing an integer representing the minimum possible perimeter of the constructed shape.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
3
4
4 1
4 5
1 1
2 3
3
2 4
2 6
2 3
1
2 65

output

1
2
3
26
24
134

Note

In the first test case, a way of getting the minimum possible perimeter is to arrange the slices of cheese as follows.

We can calculate that the perimeter of the constructed shape is \(2+5+1+1+1+1+3+1+5+1+2+3=26\). It can be shown that we cannot get a smaller perimeter.

Consider the following invalid arrangement.

Even though the perimeter of the shape above is \(24\), it does not satisfy all conditions of the problem. The bottom edge of the \(1 \times 1\) slice of cheese is not a segment of the x-axis.

In the second test case, a way of getting the minimum possible perimeter is to arrange the slices of cheese as follows.

We can calculate that the perimeter of the constructed shape is \(2+2+2+3+2+3+2+2+2+4=24\). It can be shown that we cannot get a smaller perimeter.

代码参考

Show code

CodeForces_1740Bview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
template <class Tp>
using pi = std::pair<Tp, Tp>;
template <class Tp>
using vc = std::vector<Tp>;
struct CustomHash {
  static constexpr uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static constexpr size_t append(size_t x, size_t y) {
    return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1));
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  template <class Tp, class Up>
  size_t operator()(std::pair<Tp, Up> const &p) const {
    return append((*this)(p.first), (*this)(p.second));
  }
  template <typename... Ts>
  size_t operator()(std::tuple<Ts...> const &tp) const {
    size_t ret = 0;
    std::apply(
      [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); },
      tp);
    return ret;
  }
  template <
    class Tp,
    std::enable_if_t<std::is_same_v<decltype(std::declval<Tp>().begin()),
                                    typename Tp::iterator> &&
                     std::is_same_v<decltype(std::declval<Tp>().end()),
                                    typename Tp::iterator>> * = nullptr>
  size_t operator()(Tp const &tp) const {
    size_t ret = 0;
    for (auto &&i : tp) ret = append(ret, (*this)(i));
    return ret;
  }
};
using i64 = int64_t;
using pii64 = pi<i64>;
#define for_(i, l, r, vars...)                                            \
  for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \
       i <= i##end;                                                       \
       ++i)
#define foreach_ref_(i, container) for (auto &i : (container))
#define all_(a) (a).begin(), (a).end()
#define read_var_(type, name) \
  type name;                  \
  std::cin >> name
#define read_container_(type, name, size) \
  type name(size);                        \
  foreach_ref_(i, name) std::cin >> i
template <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(Tp i) -> bool {
  return i && (i & -i) == i;
}
#define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple>>
namespace tuple_detail_ {
template <std::size_t Begin, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
apply2_impl_(BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) {
  return std::make_tuple(
    std::forward<BinOp>(f)(std::get<Is>(lhs), std::get<Is>(rhs))...);
}
}  // namespace tuple_detail_
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(Tuple &&t) {
  static_assert(Begin <= TPL_SIZE_(Tuple) && Len <= TPL_SIZE_(Tuple) &&
                  Begin + Len <= TPL_SIZE_(Tuple),
                "Out of range");
  return tuple_detail_::subtuple_impl_<Begin>(t,
                                              std::make_index_sequence<Len>());
}
template <std::size_t Pos, class Tp, class Tuple>
constexpr auto tuple_push(Tp &&v, Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        std::make_tuple(v),
                        subtuple<Pos, TPL_SIZE_(Tuple) - Pos>(t));
}
template <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_pop(Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        subtuple<Pos + 1, TPL_SIZE_(Tuple) - Pos - 1>(t));
}
template <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(BinOp &&f, Tuple &&lhs, Tuple &&rhs) {
  return tuple_detail_::apply2_impl_(
    f, lhs, rhs, std::make_index_sequence<TPL_SIZE_(Tuple)>());
}
#define OO_PTEQ_(op)                                                          \
  template <class Tp, class Up>                                               \
  constexpr auto operator op(std::pair<Tp, Up> lhs,                           \
                             const std::pair<Tp, Up> &rhs) {                  \
    return {lhs.first op rhs.first, lhs.second op rhs.second};                \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op(std::tuple<Ts...> const &lhs,                    \
                             std::tuple<Ts...> const &rhs) {                  \
    return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs);       \
  }                                                                           \
  template <class Tp, class Up>                                               \
  constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs,         \
                                              const std::pair<Tp, Up> &rhs) { \
    lhs.first op## = rhs.first;                                               \
    lhs.second op## = rhs.second;                                             \
    return lhs;                                                               \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op##=(std::tuple<Ts...> &lhs,                       \
                                const std::tuple<Ts...> &rhs) {               \
    return lhs = lhs op rhs;                                                  \
  }
OO_PTEQ_(+)
OO_PTEQ_(-)
OO_PTEQ_(*)
OO_PTEQ_(/)
OO_PTEQ_(%)
OO_PTEQ_(&)
OO_PTEQ_(|)
OO_PTEQ_(^)
OO_PTEQ_(<<)
OO_PTEQ_(>>)
#undef OO_PTEQ_
#undef TPL_SIZE_
template <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
std::ostream &operator<<(std::ostream &os, const std::pair<Tp, Up> &p) {
  return os << p.first << ' ' << p.second;
}
template <typename... Ts>
std::istream &operator>>(std::istream &is, std::tuple<Ts...> &p) {
  std::apply([&](Ts &...targs) { ((is >> targs), ...); }, p);
  return is;
}
template <typename... Ts>
std::ostream &operator<<(std::ostream &os, const std::tuple<Ts...> &p) {
  std::apply(
    [&](Ts const &...targs) {
      std::size_t n{0};
      ((os << targs << (++n != sizeof...(Ts) ? " " : "")), ...);
    },
    p);
  return os;
}
template <class Ch,
          class Tr,
          class Ct,
          std::enable_if_t<std::is_same_v<decltype(std::declval<Ct>().begin()),
                                          typename Ct::iterator> &&
                           std::is_same_v<decltype(std::declval<Ct>().end()),
                                          typename Ct::iterator>> * = nullptr>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os,
                                       const Ct &x) {
  if (x.begin() == x.end()) return os;
  for (auto it = x.begin(); it != x.end() - 1; ++it) os << *it << ' ';
  os << x.back();
  return os;
}
using namespace std;
auto solve([[maybe_unused]] int t_ = 0) -> void {
  read_var_(int, n);
  read_container_(vc<pii64>, a, n);
  for (auto &i : a)
    if (i.first < i.second) swap(i.first, i.second);
  sort(all_(a));
  i64 ans = 0;
  for_(i, 1, n - 1) ans += a[i].first - a[i - 1].first;
  for_(i, 0, n - 1) ans += 2 * a[i].second;
  cout << ans + a.front().first + a.back().first << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

C - Bricks and Bags

There are \(n\) bricks numbered from \(1\) to \(n\). Brick \(i\) has a weight of \(a_i\).

Pak Chanek has \(3\) bags numbered from \(1\) to \(3\) that are initially empty. For each brick, Pak Chanek must put it into one of the bags. After this, each bag must contain at least one brick.

After Pak Chanek distributes the bricks, Bu Dengklek will take exactly one brick from each bag. Let \(w_j\) be the weight of the brick Bu Dengklek takes from bag \(j\). The score is calculated as \(|w_1 - w_2| + |w_2 - w_3|\), where \(|x|\) denotes the absolute value of \(x\).

It is known that Bu Dengklek will take the bricks in such a way that minimises the score. What is the maximum possible final score if Pak Chanek distributes the bricks optimally?

Input

Each test contains multiple test cases. The first line contains an integer \(t\) (\(1 \leq t \leq 2 \cdot 10^4\)) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer \(n\) (\(3 \leq n \leq 2 \cdot 10^5\)) — the number of bricks.

The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^9\)) — the weights of the bricks.

It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2 \cdot 10^5\).

Output

For each test case, output a line containing an integer representing the maximum possible final score if Pak Chanek distributes the bricks optimally.

Example

input

1
2
3
4
5
6
7
3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265

output

1
2
3
6
63
0

Note

In the first test case, one way of achieving a final score of \(6\) is to do the following:

  • Put bricks \(1\), \(4\), and \(5\) into bag \(1\).
  • Put brick \(3\) into bag \(2\).
  • Put brick \(2\) into bag \(3\).

If Pak Chanek distributes the bricks that way, a way Bu Dengklek can take the bricks is:

  • Take brick \(5\) from bag \(1\).
  • Take brick \(3\) from bag \(2\).
  • Take brick \(2\) from bag \(3\).

The score is \(|a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6\). It can be shown that Bu Dengklek cannot get a smaller score from this distribution.

It can be shown that there is no other distribution that results in a final score bigger than \(6\).

代码参考

Show code

CodeForces_1740Cview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
template <class Tp>
using vc = std::vector<Tp>;
struct CustomHash {
  static constexpr uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static constexpr size_t append(size_t x, size_t y) {
    return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1));
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  template <class Tp, class Up>
  size_t operator()(std::pair<Tp, Up> const &p) const {
    return append((*this)(p.first), (*this)(p.second));
  }
  template <typename... Ts>
  size_t operator()(std::tuple<Ts...> const &tp) const {
    size_t ret = 0;
    std::apply(
      [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); },
      tp);
    return ret;
  }
  template <
    class Tp,
    std::enable_if_t<std::is_same_v<decltype(std::declval<Tp>().begin()),
                                    typename Tp::iterator> &&
                     std::is_same_v<decltype(std::declval<Tp>().end()),
                                    typename Tp::iterator>> * = nullptr>
  size_t operator()(Tp const &tp) const {
    size_t ret = 0;
    for (auto &&i : tp) ret = append(ret, (*this)(i));
    return ret;
  }
};
using i64 = int64_t;
#define foreach_ref_(i, container) for (auto &i : (container))
#define all_(a) (a).begin(), (a).end()
#define run_exec_(expressions, post_process) \
  {                                          \
    expressions;                             \
    post_process;                            \
  }
#define run_return_void_(expressions) run_exec_(expressions, return)
#define read_var_(type, name) \
  type name;                  \
  std::cin >> name
#define read_container_(type, name, size) \
  type name(size);                        \
  foreach_ref_(i, name) std::cin >> i
template <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(Tp i) -> bool {
  return i && (i & -i) == i;
}
#define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple>>
namespace tuple_detail_ {
template <std::size_t Begin, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
apply2_impl_(BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) {
  return std::make_tuple(
    std::forward<BinOp>(f)(std::get<Is>(lhs), std::get<Is>(rhs))...);
}
}  // namespace tuple_detail_
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(Tuple &&t) {
  static_assert(Begin <= TPL_SIZE_(Tuple) && Len <= TPL_SIZE_(Tuple) &&
                  Begin + Len <= TPL_SIZE_(Tuple),
                "Out of range");
  return tuple_detail_::subtuple_impl_<Begin>(t,
                                              std::make_index_sequence<Len>());
}
template <std::size_t Pos, class Tp, class Tuple>
constexpr auto tuple_push(Tp &&v, Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        std::make_tuple(v),
                        subtuple<Pos, TPL_SIZE_(Tuple) - Pos>(t));
}
template <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_pop(Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        subtuple<Pos + 1, TPL_SIZE_(Tuple) - Pos - 1>(t));
}
template <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(BinOp &&f, Tuple &&lhs, Tuple &&rhs) {
  return tuple_detail_::apply2_impl_(
    f, lhs, rhs, std::make_index_sequence<TPL_SIZE_(Tuple)>());
}
#define OO_PTEQ_(op)                                                          \
  template <class Tp, class Up>                                               \
  constexpr auto operator op(std::pair<Tp, Up> lhs,                           \
                             const std::pair<Tp, Up> &rhs) {                  \
    return {lhs.first op rhs.first, lhs.second op rhs.second};                \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op(std::tuple<Ts...> const &lhs,                    \
                             std::tuple<Ts...> const &rhs) {                  \
    return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs);       \
  }                                                                           \
  template <class Tp, class Up>                                               \
  constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs,         \
                                              const std::pair<Tp, Up> &rhs) { \
    lhs.first op## = rhs.first;                                               \
    lhs.second op## = rhs.second;                                             \
    return lhs;                                                               \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op##=(std::tuple<Ts...> &lhs,                       \
                                const std::tuple<Ts...> &rhs) {               \
    return lhs = lhs op rhs;                                                  \
  }
OO_PTEQ_(+)
OO_PTEQ_(-)
OO_PTEQ_(*)
OO_PTEQ_(/)
OO_PTEQ_(%)
OO_PTEQ_(&)
OO_PTEQ_(|)
OO_PTEQ_(^)
OO_PTEQ_(<<)
OO_PTEQ_(>>)
#undef OO_PTEQ_
#undef TPL_SIZE_
template <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
std::ostream &operator<<(std::ostream &os, const std::pair<Tp, Up> &p) {
  return os << p.first << ' ' << p.second;
}
template <typename... Ts>
std::istream &operator>>(std::istream &is, std::tuple<Ts...> &p) {
  std::apply([&](Ts &...targs) { ((is >> targs), ...); }, p);
  return is;
}
template <typename... Ts>
std::ostream &operator<<(std::ostream &os, const std::tuple<Ts...> &p) {
  std::apply(
    [&](Ts const &...targs) {
      std::size_t n{0};
      ((os << targs << (++n != sizeof...(Ts) ? " " : "")), ...);
    },
    p);
  return os;
}
template <class Ch,
          class Tr,
          class Ct,
          std::enable_if_t<std::is_same_v<decltype(std::declval<Ct>().begin()),
                                          typename Ct::iterator> &&
                           std::is_same_v<decltype(std::declval<Ct>().end()),
                                          typename Ct::iterator>> * = nullptr>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os,
                                       const Ct &x) {
  if (x.begin() == x.end()) return os;
  for (auto it = x.begin(); it != x.end() - 1; ++it) os << *it << ' ';
  os << x.back();
  return os;
}
using namespace std;
auto solve([[maybe_unused]] int t_ = 0) -> void {
  read_var_(i64, n);
  read_container_(vc<i64>, a, n);
  sort(all_(a));
  a.erase(unique(all_(a)), a.end());
  if (a.size() == 1) run_return_void_(cout << "0\n");
  if (a.size() == 2)
    run_return_void_(cout << 2 * (a.back() - a.front()) << '\n');
  i64 ans = a.back() - a.front();
  for (auto it = a.begin(); it != a.end() - 1; ++it)
    ans = max(ans, *(it + 1) + a.back() - 2 * *it);
  for (auto it = a.rbegin(); it != a.rend() - 1; ++it)
    ans = max(ans, 2 * *it - *(it + 1) - a.front());
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

D - Knowledge Cards

Pak Chanek, a renowned scholar, invented a card puzzle using his knowledge. In the puzzle, you are given a board with \(n\) rows and \(m\) columns. Let \((r, c)\) represent the cell in the \(r\)-th row and the \(c\)-th column.

Initially, there are \(k\) cards stacked in cell \((1, 1)\). Each card has an integer from \(1\) to \(k\) written on it. More specifically, the \(i\)-th card from the top of the stack in cell \((1, 1)\) has the number \(a_i\) written on it. It is known that no two cards have the same number written on them. In other words, the numbers written on the cards are a permutation of integers from \(1\) to \(k\). All other cells are empty.

You need to move the \(k\) cards to cell \((n, m)\) to create another stack of cards. Let \(b_i\) be the number written on the \(i\)-th card from the top of the stack in cell \((n, m)\). You should create the stack in cell \((n, m)\) in such a way so that \(b_i = i\) for all \(1 \leq i \leq k\).

In one move, you can remove the top card from a cell and place it onto an adjacent cell (a cell that shares a common side). If the target cell already contains one or more cards, you place your card on the top of the stack. You must do each operation while satisfying the following restrictions:

  • Each cell other than \((1,1)\) and \((n,m)\) must not have more than one card on it.
  • You cannot move a card onto cell \((1,1)\).
  • You cannot move a card from cell \((n,m)\).

Given the values of \(n\), \(m\), \(k\) and the array \(a\), determine if the puzzle is solvable.

Input

Each test contains multiple test cases. The first line contains an integer \(t\) (\(1 \leq t \leq 2 \cdot 10^4\)) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains three integers \(n\), \(m\), and \(k\) (\(3 \leq n, m \leq 10^6\), \(nm \leq 10^6\), \(1 \leq k \leq 10^5\)) — the size of the board and the number of cards.

The second line of the test case contains \(k\) integers \(a_1, a_2, \ldots, a_k\) — the array \(a\), representing the numbers written on the cards. The values of \(a\) are a permutation of integers from \(1\) to \(k\).

It is guaranteed that the sum of \(nm\) and \(k\) over all test cases do not exceed \(10^6\) and \(10^5\) respectively.

Output

For each test case, output "YA" (without quotes) if it is possible and "TIDAK" (without quotes) otherwise, which mean yes and no in Indonesian respectively.

You can output "YA" and "TIDAK" in any case (for example, strings "tiDAk", "tidak", and "Tidak" will be recognised as a negative response).

Example

input

1
2
3
4
5
6
7
8
9
4
3 3 6
3 6 4 1 2 5
3 3 10
1 2 3 4 5 6 7 8 9 10
5 4 4
2 1 3 4
3 4 10
10 4 9 3 5 6 8 2 7 1

output

1
2
3
4
YA
TIDAK
YA
YA

Note

In the first test case, the following is one way the puzzle can be done:

  • Move the card with \(3\) written on it from cell \((1, 1)\) to cell \((1, 2)\), then cell \((1, 3)\).
  • Move the card with \(6\) written on it from cell \((1, 1)\) to cell \((2, 1)\), then cell \((3, 1)\), then cell \((3, 2)\), then cell \((3, 3)\).
  • Move the card with \(4\) written on it from cell \((1, 1)\) to cell \((1, 2)\).
  • Move the card with \(1\) written on it from cell \((1, 1)\) to cell \((2, 1)\), then cell \((2, 2)\), then cell \((2, 3)\).
  • Move the card with \(2\) written on it from cell \((1, 1)\) to cell \((2, 1)\), then cell \((2, 2)\).
  • Move the card with \(5\) written on it from cell \((1, 1)\) to cell \((2, 1)\), then cell \((3, 1)\), then cell \((3, 2)\), then cell \((3, 3)\).
  • Move the card with \(2\) written on it from cell \((2, 2)\) to cell \((2, 1)\).
  • Move the card with \(4\) written on it from cell \((1, 2)\) to cell \((2, 2)\), then cell \((3, 2)\), then cell \((3, 3)\).
  • Move the card with \(3\) written on it from cell \((1, 3)\) to cell \((1, 2)\), then cell \((2, 2)\), then cell \((3, 2)\), then cell \((3, 3)\).
  • Move the card with \(2\) written on it from cell \((2, 1)\) to cell \((3, 1)\), then cell \((3, 2)\), then cell \((3, 3)\).
  • Move the card with \(1\) written on it from cell \((2, 3)\) to cell \((3, 3)\).

An animated illustration regarding the process mentioned above is as follows:

代码参考

Show code

CodeForces_1740Dview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
struct CustomHash {
  static constexpr uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static constexpr size_t append(size_t x, size_t y) {
    return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1));
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  template <class Tp, class Up>
  size_t operator()(std::pair<Tp, Up> const &p) const {
    return append((*this)(p.first), (*this)(p.second));
  }
  template <typename... Ts>
  size_t operator()(std::tuple<Ts...> const &tp) const {
    size_t ret = 0;
    std::apply(
      [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); },
      tp);
    return ret;
  }
  template <
    class Tp,
    std::enable_if_t<std::is_same_v<decltype(std::declval<Tp>().begin()),
                                    typename Tp::iterator> &&
                     std::is_same_v<decltype(std::declval<Tp>().end()),
                                    typename Tp::iterator>> * = nullptr>
  size_t operator()(Tp const &tp) const {
    size_t ret = 0;
    for (auto &&i : tp) ret = append(ret, (*this)(i));
    return ret;
  }
};
#define for_(i, l, r, vars...)                                            \
  for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \
       i <= i##end;                                                       \
       ++i)
#define run_exec_(expressions, post_process) \
  {                                          \
    expressions;                             \
    post_process;                            \
  }
#define run_continue_(expressions) run_exec_(expressions, continue)
template <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(Tp i) -> bool {
  return i && (i & -i) == i;
}
#define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple>>
namespace tuple_detail_ {
template <std::size_t Begin, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
apply2_impl_(BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) {
  return std::make_tuple(
    std::forward<BinOp>(f)(std::get<Is>(lhs), std::get<Is>(rhs))...);
}
}  // namespace tuple_detail_
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(Tuple &&t) {
  static_assert(Begin <= TPL_SIZE_(Tuple) && Len <= TPL_SIZE_(Tuple) &&
                  Begin + Len <= TPL_SIZE_(Tuple),
                "Out of range");
  return tuple_detail_::subtuple_impl_<Begin>(t,
                                              std::make_index_sequence<Len>());
}
template <std::size_t Pos, class Tp, class Tuple>
constexpr auto tuple_push(Tp &&v, Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        std::make_tuple(v),
                        subtuple<Pos, TPL_SIZE_(Tuple) - Pos>(t));
}
template <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_pop(Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        subtuple<Pos + 1, TPL_SIZE_(Tuple) - Pos - 1>(t));
}
template <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(BinOp &&f, Tuple &&lhs, Tuple &&rhs) {
  return tuple_detail_::apply2_impl_(
    f, lhs, rhs, std::make_index_sequence<TPL_SIZE_(Tuple)>());
}
#define OO_PTEQ_(op)                                                          \
  template <class Tp, class Up>                                               \
  constexpr auto operator op(std::pair<Tp, Up> lhs,                           \
                             const std::pair<Tp, Up> &rhs) {                  \
    return {lhs.first op rhs.first, lhs.second op rhs.second};                \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op(std::tuple<Ts...> const &lhs,                    \
                             std::tuple<Ts...> const &rhs) {                  \
    return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs);       \
  }                                                                           \
  template <class Tp, class Up>                                               \
  constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs,         \
                                              const std::pair<Tp, Up> &rhs) { \
    lhs.first op## = rhs.first;                                               \
    lhs.second op## = rhs.second;                                             \
    return lhs;                                                               \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op##=(std::tuple<Ts...> &lhs,                       \
                                const std::tuple<Ts...> &rhs) {               \
    return lhs = lhs op rhs;                                                  \
  }
OO_PTEQ_(+)
OO_PTEQ_(-)
OO_PTEQ_(*)
OO_PTEQ_(/)
OO_PTEQ_(%)
OO_PTEQ_(&)
OO_PTEQ_(|)
OO_PTEQ_(^)
OO_PTEQ_(<<)
OO_PTEQ_(>>)
#undef OO_PTEQ_
#undef TPL_SIZE_
template <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
std::ostream &operator<<(std::ostream &os, const std::pair<Tp, Up> &p) {
  return os << p.first << ' ' << p.second;
}
template <typename... Ts>
std::istream &operator>>(std::istream &is, std::tuple<Ts...> &p) {
  std::apply([&](Ts &...targs) { ((is >> targs), ...); }, p);
  return is;
}
template <typename... Ts>
std::ostream &operator<<(std::ostream &os, const std::tuple<Ts...> &p) {
  std::apply(
    [&](Ts const &...targs) {
      std::size_t n{0};
      ((os << targs << (++n != sizeof...(Ts) ? " " : "")), ...);
    },
    p);
  return os;
}
template <class Ch,
          class Tr,
          class Ct,
          std::enable_if_t<std::is_same_v<decltype(std::declval<Ct>().begin()),
                                          typename Ct::iterator> &&
                           std::is_same_v<decltype(std::declval<Ct>().end()),
                                          typename Ct::iterator>> * = nullptr>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os,
                                       const Ct &x) {
  if (x.begin() == x.end()) return os;
  for (auto it = x.begin(); it != x.end() - 1; ++it) os << *it << ' ';
  os << x.back();
  return os;
}
using namespace std;
auto solve([[maybe_unused]] int t_ = 0) -> void {
  int n, m, k;
  cin >> n >> m >> k;
  set<int> s;
  int now = k;
  bool gg = 0;
  for_(i, 1, k, x) {
    cin >> x;
    if (gg) continue;
    while (!s.empty() && *s.rbegin() == now) s.erase(now--);
    s.insert(x);
    if (s.size() > n * m - 3) run_continue_(gg = 1);
    while (!s.empty() && *s.rbegin() == now) s.erase(now--);
  }
  cout << (gg ? "TIDAK" : "YA") << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  int t_ = 0;
  std::cin >> t_;
  for (i_ = 0; i_ < t_; ++i_) solve(i_);
  return 0;
}

E - Hanging Hearts

Pak Chanek has \(n\) blank heart-shaped cards. Card \(1\) is attached directly to the wall while each of the other cards is hanging onto exactly one other card by a piece of string. Specifically, card \(i\) (\(i > 1\)) is hanging onto card \(p_i\) (\(p_i < i\)).

In the very beginning, Pak Chanek must write one integer number on each card. He does this by choosing any permutation \(a\) of \([1, 2, \dots, n]\). Then, the number written on card \(i\) is \(a_i\).

After that, Pak Chanek must do the following operation \(n\) times while maintaining a sequence \(s\) (which is initially empty):

  1. Choose a card \(x\) such that no other cards are hanging onto it.
  2. Append the number written on card \(x\) to the end of \(s\).
  3. If \(x \neq 1\) and the number on card \(p_x\) is larger than the number on card \(x\), replace the number on card \(p_x\) with the number on card \(x\).
  4. Remove card \(x\).

After that, Pak Chanek will have a sequence \(s\) with \(n\) elements. What is the maximum length of the longest non-decreasing subsequence\(^\dagger\) of \(s\) at the end if Pak Chanek does all the steps optimally?

\(^\dagger\) A sequence \(b\) is a subsequence of a sequence \(c\) if \(b\) can be obtained from \(c\) by deletion of several (possibly, zero or all) elements. For example, \([3,1]\) is a subsequence of \([3,2,1]\), \([4,3,1]\) and \([3,1]\), but not \([1,3,3,7]\) and \([3,10,4]\).

Input

The first line contains a single integer \(n\) (\(2 \le n \le 10^5\)) — the number of heart-shaped cards.

The second line contains \(n - 1\) integers \(p_2, p_3, \dots, p_n\) (\(1 \le p_i < i\)) describing which card that each card hangs onto.

Output

Print a single integer — the maximum length of the longest non-decreasing subsequence of \(s\) at the end if Pak Chanek does all the steps optimally.

Examples

input

1
2
6
1 2 1 4 2

output

1
4

input

1
2
2
1

output

1
2

Note

The following is the structure of the cards in the first example.

Pak Chanek can choose the permutation \(a = [1, 5, 4, 3, 2, 6]\).

Let \(w_i\) be the number written on card \(i\). Initially, \(w_i = a_i\). Pak Chanek can do the following operations in order:

  1. Select card \(5\). Append \(w_5 = 2\) to the end of \(s\). As \(w_4 > w_5\), the value of \(w_4\) becomes \(2\). Remove card \(5\). After this operation, \(s = [2]\).
  2. Select card \(6\). Append \(w_6 = 6\) to the end of \(s\). As \(w_2 \leq w_6\), the value of \(w_2\) is left unchanged. Remove card \(6\). After this operation, \(s = [2, 6]\).
  3. Select card \(4\). Append \(w_4 = 2\) to the end of \(s\). As \(w_1 \leq w_4\), the value of \(w_1\) is left unchanged. Remove card \(4\). After this operation, \(s = [2, 6, 2]\).
  4. Select card \(3\). Append \(w_3 = 4\) to the end of \(s\). As \(w_2 > w_3\), the value of \(w_2\) becomes \(4\). Remove card \(3\). After this operation, \(s = [2, 6, 2, 4]\).
  5. Select card \(2\). Append \(w_2 = 4\) to the end of \(s\). As \(w_1 \leq w_2\), the value of \(w_1\) is left unchanged. Remove card \(2\). After this operation, \(s = [2, 6, 2, 4, 4]\).
  6. Select card \(1\). Append \(w_1 = 1\) to the end of \(s\). Remove card \(1\). After this operation, \(s = [2, 6, 2, 4, 4, 1]\).

One of the longest non-decreasing subsequences of \(s = [2, 6, 2, 4, 4, 1]\) is \([2, 2, 4, 4]\). Thus, the length of the longest non-decreasing subsequence of \(s\) is \(4\). It can be proven that this is indeed the maximum possible length.

代码参考

Show code

CodeForces_1740Eview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
template <class Tp>
using vc = std::vector<Tp>;
struct CustomHash {
  static constexpr uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static constexpr size_t append(size_t x, size_t y) {
    return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1));
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  template <class Tp, class Up>
  size_t operator()(std::pair<Tp, Up> const &p) const {
    return append((*this)(p.first), (*this)(p.second));
  }
  template <typename... Ts>
  size_t operator()(std::tuple<Ts...> const &tp) const {
    size_t ret = 0;
    std::apply(
      [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); },
      tp);
    return ret;
  }
  template <
    class Tp,
    std::enable_if_t<std::is_same_v<decltype(std::declval<Tp>().begin()),
                                    typename Tp::iterator> &&
                     std::is_same_v<decltype(std::declval<Tp>().end()),
                                    typename Tp::iterator>> * = nullptr>
  size_t operator()(Tp const &tp) const {
    size_t ret = 0;
    for (auto &&i : tp) ret = append(ret, (*this)(i));
    return ret;
  }
};
#define for_(i, l, r, vars...)                                            \
  for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \
       i <= i##end;                                                       \
       ++i)
#define rfor_(i, r, l, vars...)                                           \
  for (std::make_signed_t<decltype(r - l)> i = (r), i##end = (l), ##vars; \
       i >= i##end;                                                       \
       --i)
#define read_var_(type, name) \
  type name;                  \
  std::cin >> name
template <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(Tp i) -> bool {
  return i && (i & -i) == i;
}
#define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple>>
namespace tuple_detail_ {
template <std::size_t Begin, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
apply2_impl_(BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>) {
  return std::make_tuple(
    std::forward<BinOp>(f)(std::get<Is>(lhs), std::get<Is>(rhs))...);
}
}  // namespace tuple_detail_
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(Tuple &&t) {
  static_assert(Begin <= TPL_SIZE_(Tuple) && Len <= TPL_SIZE_(Tuple) &&
                  Begin + Len <= TPL_SIZE_(Tuple),
                "Out of range");
  return tuple_detail_::subtuple_impl_<Begin>(t,
                                              std::make_index_sequence<Len>());
}
template <std::size_t Pos, class Tp, class Tuple>
constexpr auto tuple_push(Tp &&v, Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        std::make_tuple(v),
                        subtuple<Pos, TPL_SIZE_(Tuple) - Pos>(t));
}
template <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_pop(Tuple &&t) {
  static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple");
  return std::tuple_cat(subtuple<0, Pos>(t),
                        subtuple<Pos + 1, TPL_SIZE_(Tuple) - Pos - 1>(t));
}
template <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(BinOp &&f, Tuple &&lhs, Tuple &&rhs) {
  return tuple_detail_::apply2_impl_(
    f, lhs, rhs, std::make_index_sequence<TPL_SIZE_(Tuple)>());
}
#define OO_PTEQ_(op)                                                          \
  template <class Tp, class Up>                                               \
  constexpr auto operator op(std::pair<Tp, Up> lhs,                           \
                             const std::pair<Tp, Up> &rhs) {                  \
    return {lhs.first op rhs.first, lhs.second op rhs.second};                \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op(std::tuple<Ts...> const &lhs,                    \
                             std::tuple<Ts...> const &rhs) {                  \
    return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs);       \
  }                                                                           \
  template <class Tp, class Up>                                               \
  constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs,         \
                                              const std::pair<Tp, Up> &rhs) { \
    lhs.first op## = rhs.first;                                               \
    lhs.second op## = rhs.second;                                             \
    return lhs;                                                               \
  }                                                                           \
  template <class... Ts>                                                      \
  constexpr auto operator op##=(std::tuple<Ts...> &lhs,                       \
                                const std::tuple<Ts...> &rhs) {               \
    return lhs = lhs op rhs;                                                  \
  }
OO_PTEQ_(+)
OO_PTEQ_(-)
OO_PTEQ_(*)
OO_PTEQ_(/)
OO_PTEQ_(%)
OO_PTEQ_(&)
OO_PTEQ_(|)
OO_PTEQ_(^)
OO_PTEQ_(<<)
OO_PTEQ_(>>)
#undef OO_PTEQ_
#undef TPL_SIZE_
template <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
std::ostream &operator<<(std::ostream &os, const std::pair<Tp, Up> &p) {
  return os << p.first << ' ' << p.second;
}
template <typename... Ts>
std::istream &operator>>(std::istream &is, std::tuple<Ts...> &p) {
  std::apply([&](Ts &...targs) { ((is >> targs), ...); }, p);
  return is;
}
template <typename... Ts>
std::ostream &operator<<(std::ostream &os, const std::tuple<Ts...> &p) {
  std::apply(
    [&](Ts const &...targs) {
      std::size_t n{0};
      ((os << targs << (++n != sizeof...(Ts) ? " " : "")), ...);
    },
    p);
  return os;
}
template <class Ch,
          class Tr,
          class Ct,
          std::enable_if_t<std::is_same_v<decltype(std::declval<Ct>().begin()),
                                          typename Ct::iterator> &&
                           std::is_same_v<decltype(std::declval<Ct>().end()),
                                          typename Ct::iterator>> * = nullptr>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os,
                                       const Ct &x) {
  if (x.begin() == x.end()) return os;
  for (auto it = x.begin(); it != x.end() - 1; ++it) os << *it << ' ';
  os << x.back();
  return os;
}
using namespace std;
auto solve([[maybe_unused]] int t_ = 0) -> void {
  read_var_(int, n);
  vc<int> fa(n + 1);
  for_(i, 2, n) cin >> fa[i];
  vc<int> dep(n + 1, 1), f(n + 1);
  rfor_(i, n, 1) {
    chkmax(f[i], dep[i]);
    if (i > 1) {
      f[fa[i]] += f[i];
      chkmax(dep[fa[i]], dep[i] + 1);
    }
  }
  cout << f[1] << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  solve(i_);
  return 0;
}

F - Conditional Mix

Pak Chanek is given an array \(a\) of \(n\) integers. For each \(i\) (\(1 \leq i \leq n\)), Pak Chanek will write the one-element set \(\{a_i\}\) on a whiteboard.

After that, in one operation, Pak Chanek may do the following:

  1. Choose two different sets \(S\) and \(T\) on the whiteboard such that \(S \cap T = \varnothing\) (\(S\) and \(T\) do not have any common elements).
  2. Erase \(S\) and \(T\) from the whiteboard and write \(S \cup T\) (the union of \(S\) and \(T\)) onto the whiteboard.

After performing zero or more operations, Pak Chanek will construct a multiset \(M\) containing the sizes of all sets written on the whiteboard. In other words, each element in \(M\) corresponds to the size of a set after the operations.

How many distinct\(^\dagger\) multisets \(M\) can be created by this process? Since the answer may be large, output it modulo \(998\,244\,353\).

\(^\dagger\) Multisets \(B\) and \(C\) are different if and only if there exists a value \(k\) such that the number of elements with value \(k\) in \(B\) is different than the number of elements with value \(k\) in \(C\).

Input

The first line contains a single integer \(n\) (\(1 \le n \le 2000\)).

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)).

Output

Output the number of distinct multisets \(M\) modulo \(998\,244\,353\).

Examples

input

1
2
6
1 1 2 1 4 3

output

1
7

input

1
2
7
3 5 4 3 7 4 5

output

1
11

Note

In the first example, the possible multisets \(M\) are \(\{1,1,1,1,1,1\}\), \(\{1,1,1,1,2\}\), \(\{1,1,1,3\}\), \(\{1,1,2,2\}\), \(\{1,1,4\}\), \(\{1,2,3\}\), and \(\{2,2,2\}\).

As an example, let's consider a possible sequence of operations.

  1. In the beginning, the sets are \(\{1\}\), \(\{1\}\), \(\{2\}\), \(\{1\}\), \(\{4\}\), and \(\{3\}\).
  2. Do an operation on sets \(\{1\}\) and \(\{3\}\). Now, the sets are \(\{1\}\), \(\{1\}\), \(\{2\}\), \(\{4\}\), and \(\{1,3\}\).
  3. Do an operation on sets \(\{2\}\) and \(\{4\}\). Now, the sets are \(\{1\}\), \(\{1\}\), \(\{1,3\}\), and \(\{2,4\}\).
  4. Do an operation on sets \(\{1,3\}\) and \(\{2,4\}\). Now, the sets are \(\{1\}\), \(\{1\}\), and \(\{1,2,3,4\}\).
  5. The multiset \(M\) that is constructed is \(\{1,1,4\}\).

代码参考

Show code

G - Dangerous Laser Power

Pak Chanek has an \(n \times m\) grid of portals. The portal on the \(i\)-th row and \(j\)-th column is denoted as portal \((i,j)\). The portals \((1,1)\) and \((n,m)\) are on the north-west and south-east corner of the grid respectively.

The portal \((i,j)\) has two settings:

  • Type \(t_{i,j}\), which is either \(0\) or \(1\).
  • Strength \(s_{i,j}\), which is an integer between \(1\) and \(10^9\) inclusive.

Each portal has \(4\) faces labelled with integers \(0,1,2,3\), which correspond to the north, east, south, and west direction respectively.

When a laser enters face \(k\) of portal \((i, j)\) with speed \(x_\text{in}\), it leaves the portal going out of face \((k+2+t_{i,j}) \bmod 4\) with speed \(x_\text{out} = \max(x_\text{in},s_{i,j})\). The portal also has to consume \(x_\text{out} - x_\text{in}\) units of energy.

Pak Chanek is very bored today. He will shoot \(4nm\) lasers with an initial speed of \(1\), one into each face of each portal. Each laser will travel throughout this grid of portals until it moves outside the grid or it has passed through \(10^{100}\) portals.

At the end, Pak Chanek thinks that a portal is good if and only if the total energy consumed by that portal modulo \(2\) is equal to its type. Given the strength settings of all portals, find a way to assign the type settings of each portal such that the number of good portals is maximised.

Input

The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 1000\)) — the number of rows and columns in the grid.

The \(i\)-th of the next \(n\) lines contains \(m\) integers, with the \(j\)-th integer being \(s_{i,j}\) (\(1 \leq s_{i,j} \leq 10^9\)) — the strength of portal \((i, j)\).

Output

Print \(n\) lines with each line containing a string of length \(m\) consisting of characters \(0\) or \(1\) representing the type settings. The \(j\)-th character in the \(i\)-th string is the type setting of portal \((i, j)\).

If there are multiple solutions, you can output any of them.

Examples

input

1
2
3
2 3
8 8 2
6 5 7

output

1
2
110
100

input

1
2
1 2
420 69

output

1
10

Note

In the first example, let's consider the laser Pak Chanek shoots into face \(1\) of portal \((2, 2)\). The laser travels as follows:

  1. The laser enters face \(1\) of portal \((2, 2)\) with speed \(1\). It leaves the portal going out of face \(3\) with speed \(5\). Portal \((2, 2)\) consumes \(4\) units of energy.
  2. The laser enters face \(1\) of portal \((2, 1)\) with speed \(5\). It leaves the portal going out of face \(0\) with speed \(6\). Portal \((2, 1)\) consumes \(1\) units of energy.
  3. The laser enters face \(2\) of portal \((1, 1)\) with speed \(6\). It leaves the portal going out of face \(1\) with speed \(8\). Portal \((1, 1)\) consumes \(2\) units of energy.
  4. The laser enters face \(3\) of portal \((1, 2)\) with speed \(8\). It leaves the portal going out of face \(2\) with speed \(8\). Portal \((1, 2)\) consumes \(0\) units of energy.
  5. The laser enters face \(0\) of portal \((2, 2)\) with speed \(8\). It leaves the portal going out of face \(2\) with speed \(8\). Portal \((2, 2)\) consumes \(0\) units of energy.

The illustration of the travel of the laser above is as follows.

As an example, consider portal \((2, 3)\). We can calculate that the total energy consumed by that portal in the end will be \(32\). Since \(32 \bmod 2 = 0\) and \(t_{2,3} = 0\), then it is a good portal.

代码参考

Show code

H - MEX Tree Manipulation

Given a rooted tree, define the value of vertex \(u\) in the tree recursively as the MEX\(^\dagger\) of the values of its children. Note that it is only the children, not all of its descendants. In particular, the value of a leaf is \(0\).

Pak Chanek has a rooted tree that initially only contains a single vertex with index \(1\), which is the root. Pak Chanek is going to do \(q\) queries. In the \(i\)-th query, Pak Chanek is given an integer \(x_i\). Pak Chanek needs to add a new vertex with index \(i+1\) as the child of vertex \(x_i\). After adding the new vertex, Pak Chanek needs to recalculate the values of all vertices and report the sum of the values of all vertices in the current tree.

\(^\dagger\) The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For example, the MEX of \([0,1,1,2,6,7]\) is \(3\) and the MEX of \([6,9]\) is \(0\).

Input

The first line contains a single integer \(q\) (\(1 \le q \le 3 \cdot 10^5\)) — the number of operations.

Each of the next \(q\) lines contains a single integer \(x_i\) (\(1 \leq x_i \leq i\)) — the description of the \(i\)-th query.

Output

For each query, print a line containing an integer representing the sum of the new values of all vertices in the tree after adding the vertex.

Examples

input

1
2
3
4
5
6
7
8
7
1
1
3
2
5
2
1

output

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

input

1
2
3
4
5
6
7
8
9
8
1
1
1
1
5
6
7
8

output

1
2
3
4
5
6
7
8
1
1
1
1
3
2
4
3

Note

In the first example, the tree after the \(6\)-th query will look like this.

  • Vertex \(7\) is a leaf, so its value is \(0\).
  • Vertex \(6\) is a leaf, so its value is \(0\).
  • Vertex \(5\) only has a child with value \(0\), so its value is \(1\).
  • Vertex \(4\) is a leaf, so its value is \(0\).
  • Vertex \(3\) only has a child with value \(0\), so its value is \(1\).
  • Vertex \(2\) has children with values \(0\) and \(1\), so its value is \(2\).
  • Vertex \(1\) has children with values \(1\) and \(2\), so its value is \(0\).

The sum of the values of all vertices is \(0+0+1+0+1+2+0=4\).

代码参考

Show code

I - Arranging Crystal Balls

In the world of Compfestnesia, Pak Chanek discovers a secret underground dungeon. Inside it, there is a treasure chest that is surrounded by \(n\) statues that are arranged in a circular manner. The statues are numbered from \(0\) to \(n-1\) with statue \(i\) being to the left of statue \(i+1\) and statue \(n-1\) being to the left of statue \(0\).

Pak Chanek observes that each statue is holding a crystal ball with an integer between \(0\) and \(m-1\) inclusive. Let's say the integer in the crystal ball of statue \(i\) is \(a_i\).

The dungeon provides instructions that every integer in the crystal balls must be \(0\) in order to open the treasure chest. To achieve that, Pak Chanek is given an integer \(k\), and he can do zero or more operations. In a single operation, Pak Chanek does the following:

  1. Choose exactly \(k\) consecutive statues. In other words, choose the statues \(p, (p+1) \bmod n, (p+2) \bmod n, (p+3) \bmod n, \ldots, (p+k-1) \bmod n\) for some chosen index \(p\).
  2. Do one of the following:
    • For all chosen statues, change their values of \(a_i\) into \((a_i+1) \bmod m\).
    • For all chosen statues, change their values of \(a_i\) into \((a_i-1) \bmod m\).

Help Pak Chanek find the minimum possible number of operations to open the treasure chest.

Input

The first line contains three integers \(n\), \(m\), and \(k\) (\(2 \leq n,m \leq 10^6\), \(nm \leq 2 \cdot 10^6\), \(1 \leq k < n\)) — the number of statues, the bound of the integers in the crystal balls, and the number of statues that can be operated in a single operation.

The second line contains \(n\) integers \(a_0,a_1,\ldots,a_{n-1}\) (\(0 \leq a_i < m\)) — the integers in the crystal balls.

Output

If it is possible to perform zero or more operations so that \(a_0=a_1=\ldots=a_{n-1}=0\), output the minimum number of operations required. Otherwise, output \(-1\).

Examples

input

1
2
5 9 3
8 1 4 5 0

output

1
7

input

1
2
4 4 2
1 0 0 0

output

1
-1

input

1
2
5 5 2
1 0 0 0 0

output

1
10

Note

In the first example, Pak Chanek can do the following operations:

  1. Do the \(a_i := (a_i-1) \bmod m\) operation \(3\) times for statues \(1\), \(2\), and \(3\). Now \(a=[8,7,1,2,0]\).
  2. Do the \(a_i := (a_i-1) \bmod m\) operation \(1\) time for statues \(3\), \(4\), and \(0\). Now \(a=[7,7,1,1,8]\).
  3. Do the \(a_i := (a_i+1) \bmod m\) operation \(2\) times for statues \(4\), \(0\), and \(1\). Now \(a=[0,0,1,1,1]\).
  4. Do the \(a_i := (a_i-1) \bmod m\) operation \(1\) time for statues \(2\), \(3\), and \(4\). Now \(a=[0,0,0,0,0]\).

代码参考

Show code