QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325608#8231. Festival Decoratinghos_lyricWA 719ms20396kbC++1410.9kb2024-02-11 17:50:552024-10-20 20:06:14

Judging History

你现在查看的是最新测评结果

  • [2024-10-20 20:06:14]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:WA
  • 用时:719ms
  • 内存:20396kb
  • [2024-10-20 19:52:41]
  • hack成功,自动添加数据
  • (/hack/1018)
  • [2024-02-11 17:50:55]
  • 评测
  • 测评结果:100
  • 用时:626ms
  • 内存:20308kb
  • [2024-02-11 17:50:55]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353U;
constexpr unsigned MO2 = 2U * MO;
constexpr int FFT_MAX = 23;
using Mint = ModInt<MO>;
constexpr Mint FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 911660635U, 372528824U, 929031873U, 452798380U, 922799308U, 781712469U, 476477967U, 166035806U, 258648936U, 584193783U, 63912897U, 350007156U, 666702199U, 968855178U, 629671588U, 24514907U, 996173970U, 363395222U, 565042129U, 733596141U, 267099868U, 15311432U};
constexpr Mint INV_FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 86583718U, 509520358U, 337190230U, 87557064U, 609441965U, 135236158U, 304459705U, 685443576U, 381598368U, 335559352U, 129292727U, 358024708U, 814576206U, 708402881U, 283043518U, 3707709U, 121392023U, 704923114U, 950391366U, 428961804U, 382752275U, 469870224U};
constexpr Mint FFT_RATIOS[FFT_MAX] = {911660635U, 509520358U, 369330050U, 332049552U, 983190778U, 123842337U, 238493703U, 975955924U, 603855026U, 856644456U, 131300601U, 842657263U, 730768835U, 942482514U, 806263778U, 151565301U, 510815449U, 503497456U, 743006876U, 741047443U, 56250497U, 867605899U};
constexpr Mint INV_FFT_RATIOS[FFT_MAX] = {86583718U, 372528824U, 373294451U, 645684063U, 112220581U, 692852209U, 155456985U, 797128860U, 90816748U, 860285882U, 927414960U, 354738543U, 109331171U, 293255632U, 535113200U, 308540755U, 121186627U, 608385704U, 438932459U, 359477183U, 824071951U, 103369235U};

// as[rev(i)] <- \sum_j \zeta^(ij) as[j]
void fft(Mint *as, int n) {
  assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << FFT_MAX);
  int m = n;
  if (m >>= 1) {
    for (int i = 0; i < m; ++i) {
      const unsigned x = as[i + m].x;  // < MO
      as[i + m].x = as[i].x + MO - x;  // < 2 MO
      as[i].x += x;  // < 2 MO
    }
  }
  if (m >>= 1) {
    Mint prod = 1U;
    for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
      for (int i = i0; i < i0 + m; ++i) {
        const unsigned x = (prod * as[i + m]).x;  // < MO
        as[i + m].x = as[i].x + MO - x;  // < 3 MO
        as[i].x += x;  // < 3 MO
      }
      prod *= FFT_RATIOS[__builtin_ctz(++h)];
    }
  }
  for (; m; ) {
    if (m >>= 1) {
      Mint prod = 1U;
      for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
        for (int i = i0; i < i0 + m; ++i) {
          const unsigned x = (prod * as[i + m]).x;  // < MO
          as[i + m].x = as[i].x + MO - x;  // < 4 MO
          as[i].x += x;  // < 4 MO
        }
        prod *= FFT_RATIOS[__builtin_ctz(++h)];
      }
    }
    if (m >>= 1) {
      Mint prod = 1U;
      for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
        for (int i = i0; i < i0 + m; ++i) {
          const unsigned x = (prod * as[i + m]).x;  // < MO
          as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x;  // < 2 MO
          as[i + m].x = as[i].x + MO - x;  // < 3 MO
          as[i].x += x;  // < 3 MO
        }
        prod *= FFT_RATIOS[__builtin_ctz(++h)];
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x;  // < 2 MO
    as[i].x = (as[i].x >= MO) ? (as[i].x - MO) : as[i].x;  // < MO
  }
}

// as[i] <- (1/n) \sum_j \zeta^(-ij) as[rev(j)]
void invFft(Mint *as, int n) {
  assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << FFT_MAX);
  int m = 1;
  if (m < n >> 1) {
    Mint prod = 1U;
    for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
      for (int i = i0; i < i0 + m; ++i) {
        const unsigned long long y = as[i].x + MO - as[i + m].x;  // < 2 MO
        as[i].x += as[i + m].x;  // < 2 MO
        as[i + m].x = (prod.x * y) % MO;  // < MO
      }
      prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];
    }
    m <<= 1;
  }
  for (; m < n >> 1; m <<= 1) {
    Mint prod = 1U;
    for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
      for (int i = i0; i < i0 + (m >> 1); ++i) {
        const unsigned long long y = as[i].x + MO2 - as[i + m].x;  // < 4 MO
        as[i].x += as[i + m].x;  // < 4 MO
        as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x;  // < 2 MO
        as[i + m].x = (prod.x * y) % MO;  // < MO
      }
      for (int i = i0 + (m >> 1); i < i0 + m; ++i) {
        const unsigned long long y = as[i].x + MO - as[i + m].x;  // < 2 MO
        as[i].x += as[i + m].x;  // < 2 MO
        as[i + m].x = (prod.x * y) % MO;  // < MO
      }
      prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];
    }
  }
  if (m < n) {
    for (int i = 0; i < m; ++i) {
      const unsigned y = as[i].x + MO2 - as[i + m].x;  // < 4 MO
      as[i].x += as[i + m].x;  // < 4 MO
      as[i + m].x = y;  // < 4 MO
    }
  }
  const Mint invN = Mint(n).inv();
  for (int i = 0; i < n; ++i) {
    as[i] *= invN;
  }
}

void fft(vector<Mint> &as) {
  fft(as.data(), as.size());
}
void invFft(vector<Mint> &as) {
  invFft(as.data(), as.size());
}

vector<Mint> convolve(vector<Mint> as, vector<Mint> bs) {
  if (as.empty() || bs.empty()) return {};
  const int len = as.size() + bs.size() - 1;
  int n = 1;
  for (; n < len; n <<= 1) {}
  as.resize(n); fft(as);
  bs.resize(n); fft(bs);
  for (int i = 0; i < n; ++i) as[i] *= bs[i];
  invFft(as);
  as.resize(len);
  return as;
}
vector<Mint> square(vector<Mint> as) {
  if (as.empty()) return {};
  const int len = as.size() + as.size() - 1;
  int n = 1;
  for (; n < len; n <<= 1) {}
  as.resize(n); fft(as);
  for (int i = 0; i < n; ++i) as[i] *= as[i];
  invFft(as);
  as.resize(len);
  return as;
}
////////////////////////////////////////////////////////////////////////////////

#include <chrono>
#ifdef LOCAL
mt19937_64 rng(58);
#else
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif


constexpr int INF = 1001001001;

int N, Q;
vector<int> X, C;
vector<int> D;

int main() {
  for (; ~scanf("%d%d", &N, &Q); ) {
    X.assign(N + 1, 0);
    C.assign(N + 1, 0);
    for (int u = 1; u <= N; ++u) {
      scanf("%d%d", &X[u], &C[u]);
    }
    D.resize(Q);
    for (int q = 0; q < Q; ++q) {
      scanf("%d", &D[q]);
    }
    
    const int lim = *max_element(X.begin(), X.end()) + 5;
    vector<int> ans(lim, INF);
    
    // 1.5: [1, 3]
    for (int uL = 1, uR; uL < N; uL = uR) {
      uR = min(3 * uL, N) + 1;
      // rs[u] (C[u] - C[v])
      vector<Mint> rs(N + 1);
      for (int u = uL; u < uR; ++u) rs[u] = (unsigned long long)rng();
      vector<Mint> fss[4];
      for (int h = 0; h < 4; ++h) fss[h].assign(lim, 0);
      for (int u = 1; u <= N; ++u) {
        fss[0][X[u]] += 1;
        fss[1][X[u]] += C[u];
        if (uL <= u && u < uR) {
          fss[2][X[u]] += rs[u];
          fss[3][X[u]] += rs[u] * C[u];
        }
      }
      for (int h = 2; h < 4; ++h) reverse(fss[h].begin(), fss[h].end());
      const auto prod03 = convolve(fss[0], fss[3]);
      const auto prod12 = convolve(fss[1], fss[2]);
      for (int d = 1; d < lim; ++d) {
        if (prod03[lim - 1 + d] != prod12[lim - 1 + d]) {
// cerr<<uL<<" "<<uR<<" "<<d<<endl;
          chmin(ans[d], uL);
        }
      }
    }
    
    for (int q = 0; q < Q; ++q) {
      if (D[q] < lim && ans[D[q]] < INF) {
        printf("%.1f\n", 1.5 * ans[D[q]]);
      } else {
        puts("0");
      }
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4088kb

input:

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

output:

1.5
1.5
1.5
1.5
0

result:

ok 5 numbers

Test #2:

score: 0
Accepted
time: 240ms
memory: 9648kb

input:

10000 99999
67296 2
19835 1
93435 1
12756 2
38971 2
58322 2
4419 1
58583 1
68865 1
14192 1
66909 1
31419 2
40656 2
60289 2
79053 1
82880 1
28930 2
46115 1
9805 1
45096 2
29874 1
37171 2
55385 2
69812 1
16845 2
36030 2
58316 1
53401 1
35239 1
40363 1
29811 2
46440 2
98911 1
86466 2
9707 1
41909 2
616...

output:

60.0
60.0
19.5
60.0
60.0
6.0
1.5
19.5
19.5
1.5
1.5
19.5
19.5
60.0
6.0
6.0
19.5
6.0
60.0
1.5
60.0
1.5
1.5
6.0
19.5
6.0
6.0
19.5
19.5
60.0
19.5
60.0
6.0
6.0
6.0
1.5
19.5
6.0
19.5
60.0
19.5
6.0
19.5
6.0
6.0
6.0
6.0
1.5
19.5
6.0
19.5
6.0
19.5
19.5
19.5
19.5
6.0
60.0
60.0
19.5
19.5
19.5
19.5
19.5
19.5
1....

result:

ok 99999 numbers

Test #3:

score: 0
Accepted
time: 263ms
memory: 9892kb

input:

30000 99999
51883 1
2142 1
69096 2
63011 1
70418 2
56529 1
65292 2
28901 2
78364 1
96477 1
43396 2
84388 1
29343 2
41141 2
94692 1
91222 1
30872 2
17288 2
11547 1
81095 2
16542 1
38652 1
54120 2
83684 2
70599 1
55085 1
91457 1
37800 1
46297 1
81164 1
79807 2
58484 1
43670 1
7180 2
58437 1
96924 2
63...

output:

1.5
1.5
1.5
19.5
6.0
6.0
19.5
6.0
1.5
6.0
1.5
6.0
6.0
6.0
19.5
1.5
6.0
1.5
6.0
1.5
1.5
1.5
19.5
6.0
6.0
1.5
6.0
1.5
1.5
1.5
6.0
6.0
1.5
1.5
19.5
6.0
19.5
6.0
1.5
6.0
1.5
1.5
6.0
6.0
6.0
6.0
1.5
6.0
1.5
1.5
6.0
6.0
19.5
1.5
6.0
6.0
1.5
6.0
6.0
1.5
19.5
19.5
6.0
6.0
1.5
1.5
6.0
19.5
6.0
1.5
1.5
1.5
6....

result:

ok 99999 numbers

Test #4:

score: 0
Accepted
time: 630ms
memory: 18576kb

input:

100000 249999
101558 1
226768 2
215012 1
223802 2
3723 1
154951 1
95152 1
188191 2
128933 2
30706 1
141077 1
8377 2
160084 2
56011 1
11556 1
233668 2
42420 2
78212 1
245580 1
25824 2
61180 1
178193 2
179736 1
25607 2
160052 2
56056 2
93163 1
206849 2
28049 2
120634 2
44385 1
188594 1
195761 2
143744...

output:

6.0
6.0
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
6.0
1.5
6.0
1.5
6.0
19.5
1.5
1.5
1.5
6.0
1.5
1.5
6.0
1.5
19.5
19.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
6.0
6.0
6.0
1.5
1.5
6.0
6.0
1.5
6.0
1.5
6.0
6.0
6.0
19.5
6.0
1.5
6.0
1.5
6.0
1.5
6.0
6.0
1.5
1.5
6.0
1.5
6.0
6.0
19.5
6.0
6.0
1.5
1.5
6.0
6.0
1.5
1.5
6.0
1.5...

result:

ok 249999 numbers

Test #5:

score: 0
Accepted
time: 631ms
memory: 19084kb

input:

150000 249999
29678 2
204012 1
242341 1
55873 2
133195 1
191930 2
158651 2
118376 2
166685 2
52303 2
77713 1
201614 2
135192 2
195257 1
42453 1
42856 1
205245 1
86911 2
192969 1
30106 1
78525 2
140326 2
144700 1
42186 1
215224 2
19113 2
160246 1
159685 1
10602 1
137178 1
102450 1
137587 2
171123 2
1...

output:

1.5
6.0
1.5
1.5
1.5
1.5
6.0
6.0
6.0
6.0
1.5
1.5
1.5
1.5
6.0
1.5
1.5
6.0
6.0
1.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
6.0
1.5
6.0
1.5
1.5
6.0
6.0
6.0
1.5
1.5
6.0
6.0
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
19.5
1.5
1.5
6.0
6.0
6.0
1.5
6.0
1.5
6.0
6.0
1.5
1.5
1.5
1.5
6.0
6.0
6.0...

result:

ok 249999 numbers

Test #6:

score: 0
Accepted
time: 639ms
memory: 19432kb

input:

200000 249999
6248 1
183259 1
153451 2
85616 1
114994 2
98565 1
151656 1
220307 1
178381 2
11378 2
229267 2
229745 2
121994 2
127081 1
49355 1
227953 2
110071 1
227824 1
18185 2
140762 2
98797 1
3337 1
229512 2
31126 2
180753 1
206940 1
130823 2
115947 2
201783 1
113674 2
155525 2
112976 2
66144 1
1...

output:

1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
6.0
1.5
...

result:

ok 249999 numbers

Test #7:

score: 0
Accepted
time: 643ms
memory: 20156kb

input:

250000 249999
43395 2
176047 2
182604 2
174584 1
84087 1
171284 2
62939 2
167394 1
91843 1
6316 1
172364 1
60476 1
137969 2
164958 1
49683 2
230414 1
106627 1
120532 1
245073 2
179049 2
34146 2
88698 1
150706 1
99450 1
241792 2
70708 1
69060 2
175739 1
38005 2
65970 1
66335 2
182109 1
32837 1
71265 ...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
6.0
...

result:

ok 249999 numbers

Test #8:

score: 0
Accepted
time: 632ms
memory: 18356kb

input:

100000 249999
15193 3
145839 3
79432 1
108888 2
236993 3
238864 2
96951 2
249086 3
46743 1
32398 3
138017 3
52120 2
230778 2
21656 3
62564 3
208611 2
108357 1
235637 2
247827 1
247624 2
128781 2
13021 1
55702 2
43874 1
126878 2
177432 3
30826 3
100406 3
7564 1
201946 2
52522 3
249872 1
79661 3
13976...

output:

6.0
6.0
1.5
1.5
1.5
1.5
1.5
6.0
1.5
6.0
1.5
1.5
6.0
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
6.0
6.0
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
1.5
1.5
1.5
19.5
1.5
1.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
6.0
6.0
1.5
1.5
6.0
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
1.5
1.5
19.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1....

result:

ok 249999 numbers

Test #9:

score: 0
Accepted
time: 643ms
memory: 19020kb

input:

150000 249999
151797 3
132264 2
228119 2
62624 3
122655 1
93048 2
120758 3
96298 1
127189 3
79578 1
233029 1
166678 2
73775 2
132317 2
51322 1
6343 1
176933 2
106261 1
36493 2
159428 3
112870 3
117448 3
93008 1
154295 2
190828 2
74969 1
240852 1
46624 2
241429 3
65645 1
212721 2
110548 2
118236 2
20...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
6.0
6.0
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
6.0
1.5
6.0
1.5
6.0
6.0
1.5
6.0
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
...

result:

ok 249999 numbers

Test #10:

score: 0
Accepted
time: 646ms
memory: 19448kb

input:

200000 249999
47041 3
73295 1
221000 1
53265 2
201031 3
222816 2
231867 2
175711 2
150407 1
172427 1
241001 2
192843 2
13671 1
231028 3
208391 2
171533 2
166545 2
97954 3
192317 2
208872 1
231857 1
113741 1
219000 1
192008 3
112701 1
244639 3
224948 1
13585 2
184997 1
179230 3
149300 1
169950 1
9416...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #11:

score: 0
Accepted
time: 655ms
memory: 20296kb

input:

250000 249999
18119 2
48006 3
232814 2
214885 3
10886 3
761 1
28565 2
127342 3
100481 2
91912 2
169408 3
198992 3
32749 2
20324 3
32474 1
38005 2
240939 2
215900 2
200682 1
432 1
5669 3
84940 3
56161 1
203677 1
241950 1
113041 1
138836 3
153159 3
81938 1
61416 3
239183 2
180390 3
83045 3
107312 1
22...

output:

1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #12:

score: 0
Accepted
time: 635ms
memory: 18356kb

input:

100000 249999
224336 2
97421 4
237741 10
33517 3
217556 5
236052 6
13864 5
189562 1
209432 1
150833 7
94408 10
220716 3
83847 9
61678 7
95666 3
36542 1
162104 1
158517 6
33248 8
43402 1
18134 8
112042 9
202559 9
183144 6
24872 6
27758 7
217309 8
73017 1
59520 9
187721 10
100252 6
138484 7
165554 7
1...

output:

6.0
6.0
6.0
1.5
1.5
6.0
1.5
1.5
6.0
1.5
1.5
6.0
6.0
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
1.5
6.0
1.5
6.0
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
6.0
1.5
6.0
1.5
1.5
6.0
1.5
1.5
6.0
1.5
1.5
1.5
1.5
6.0
6.0
1.5
6.0
1.5
1.5
...

result:

ok 249999 numbers

Test #13:

score: 0
Accepted
time: 633ms
memory: 19076kb

input:

150000 249999
166792 6
238330 4
84379 10
131925 6
168914 7
96461 6
127762 9
204071 4
243519 8
198906 6
161831 7
131281 8
115061 10
69493 4
208817 9
4190 10
195480 10
51511 6
80200 5
81104 6
131338 8
100895 2
207427 4
237681 3
206143 4
224139 6
17948 8
228982 10
200256 8
36233 9
146742 6
162442 2
165...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
6.0
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #14:

score: 0
Accepted
time: 647ms
memory: 19676kb

input:

200000 249999
200627 8
155259 8
116629 3
7460 8
212178 2
236426 2
247999 4
58552 9
226174 3
136423 3
68187 1
223717 1
115991 3
96943 9
99300 3
196487 3
82852 9
21321 8
146283 2
173037 8
22904 7
198079 10
22919 1
95543 6
237838 2
248787 7
186160 8
201677 8
44573 7
55166 3
60479 6
247478 2
247081 10
3...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #15:

score: 0
Accepted
time: 688ms
memory: 20220kb

input:

250000 249999
14095 6
220950 6
234662 3
35913 1
132258 4
200544 10
135104 7
148916 1
13117 5
190176 9
222898 8
91946 4
178090 4
18354 1
151369 2
12233 6
228757 6
161742 7
33667 9
79810 1
74379 10
162789 3
196843 7
223296 9
78881 10
103789 5
84979 7
234254 5
80219 2
27415 7
65636 6
245431 4
16975 7
2...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #16:

score: 0
Accepted
time: 680ms
memory: 20368kb

input:

250000 249999
234423 1
106490 1
209289 1
86924 1
54501 1
166355 1
228761 1
165944 1
172158 1
64661 1
167348 1
196763 1
98465 1
56621 1
138329 1
149908 1
58448 1
231726 1
171821 1
203962 1
80624 1
299 1
16257 1
193382 1
226372 1
103199 1
160198 1
206884 1
43643 1
246448 1
197980 1
164317 1
228968 1
1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 249999 numbers

Test #17:

score: 0
Accepted
time: 641ms
memory: 18352kb

input:

100000 249999
93220 59
126118 58
114760 31
127602 91
78964 37
107468 28
17418 34
20051 6
25078 32
238158 11
143557 45
177110 45
101603 44
55221 8
27168 33
12698 44
96309 71
228393 7
85535 53
161888 73
97093 73
177327 72
151564 44
113400 33
80491 47
62362 93
15475 4
134593 67
204219 69
128232 67
1335...

output:

1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #18:

score: 0
Accepted
time: 635ms
memory: 19024kb

input:

150000 249999
104484 72
183971 17
236903 47
85763 51
109721 7
115135 100
162866 62
13428 6
134736 85
108324 46
94466 1
175154 17
72231 54
166036 34
198137 84
146960 74
90976 26
210020 89
205699 80
7068 76
192964 51
93065 27
166315 35
80521 64
41842 13
83346 79
119551 5
96204 72
97493 66
92835 15
312...

output:

1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
...

result:

ok 249999 numbers

Test #19:

score: 0
Accepted
time: 646ms
memory: 19460kb

input:

200000 249999
47102 39
120564 49
211340 98
112018 76
128324 79
13658 56
145481 5
212577 92
153372 83
195457 13
67116 53
183188 95
159717 50
223315 42
123415 47
143994 74
39260 51
58850 22
198700 27
22129 53
244348 12
112600 33
93161 52
165358 80
162648 46
238139 8
224484 6
236710 2
45342 99
44056 3
...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #20:

score: 0
Accepted
time: 699ms
memory: 20360kb

input:

250000 249999
113549 52
245740 8
25655 22
218082 47
132245 45
218861 28
37315 30
111164 95
14826 36
107398 37
156792 14
48628 66
132434 72
28151 59
158589 94
7348 97
56728 5
190552 8
170423 55
65115 44
106177 86
202419 88
183685 47
200452 7
72434 8
161099 94
95797 19
92937 7
75848 100
238323 38
1721...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #21:

score: 0
Accepted
time: 630ms
memory: 18460kb

input:

100000 249999
215178 78
137308 320
85918 996
37671 196
229886 523
231932 923
231942 388
174478 949
3670 606
187312 514
113705 684
239037 255
207483 436
54280 528
227569 162
29778 206
139135 341
39789 362
191291 41
102694 729
208895 941
57449 360
30418 630
123629 754
39958 20
220635 888
43818 148
531...

output:

1.5
1.5
1.5
1.5
6.0
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
6.0
1.5
6.0
6.0
1.5
6.0
1.5
1.5
1.5
1.5
1.5
6.0
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
6.0
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
6.0
1.5
1.5
1.5
1.5
6.0
...

result:

ok 249999 numbers

Test #22:

score: 0
Accepted
time: 644ms
memory: 19012kb

input:

150000 249999
168799 574
236614 391
5626 61
80977 154
38826 825
210532 62
100484 431
137419 781
103555 171
155556 287
247529 26
33559 487
177031 92
195197 875
91976 329
199343 636
83803 545
106072 247
123800 617
25942 788
235116 540
75666 678
240796 87
116602 682
229461 207
234450 428
235548 279
159...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #23:

score: 0
Accepted
time: 654ms
memory: 19548kb

input:

200000 249999
220479 940
50222 148
184880 27
222833 69
4952 631
43460 820
140864 16
15536 585
121758 416
81558 785
139693 320
164815 379
6191 763
223454 81
202200 271
68519 74
25162 498
51853 454
170830 650
123228 426
131945 392
191834 517
152172 502
117499 506
103682 415
245558 424
146040 951
87752...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #24:

score: 0
Accepted
time: 637ms
memory: 20172kb

input:

250000 249999
71099 140
102518 514
183279 196
9460 731
155766 741
159169 471
240491 548
72124 713
92079 572
102680 262
27525 958
1818 610
245646 611
85560 428
14629 438
195435 311
30920 702
105014 531
9136 11
134312 381
88919 991
56603 642
102308 551
68202 138
12583 498
88565 667
69470 82
213748 540...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #25:

score: 0
Accepted
time: 626ms
memory: 18460kb

input:

100000 249999
143875 3079
35794 9717
78870 1826
154059 3784
185253 1989
50422 6248
142560 6933
142367 7270
199873 8171
232637 2149
766 6740
128174 8273
174253 2020
71559 974
33140 3168
247328 4196
235516 7852
118076 6395
165442 1875
15428 8418
143016 5686
122930 6
97686 6807
215402 719
152923 7495
1...

output:

1.5
6.0
1.5
6.0
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
6.0
6.0
6.0
6.0
6.0
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
6.0
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
6.0
1.5
6.0
1.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
1.5
...

result:

ok 249999 numbers

Test #26:

score: 0
Accepted
time: 700ms
memory: 19152kb

input:

150000 249999
208515 1037
226810 8037
78579 8990
196348 454
52075 3057
210394 7076
132508 6037
33903 3827
45161 3699
181439 3102
81472 8711
241071 8091
177966 9734
10995 5634
142541 4395
150681 2847
64108 3634
236691 6727
44362 3578
91381 3400
115765 7253
95492 6997
86886 4546
137861 3681
89217 9885...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #27:

score: 0
Accepted
time: 648ms
memory: 19496kb

input:

200000 249999
19515 6770
260 7289
46752 6511
235290 1326
69396 2617
218263 711
68770 3615
160983 5021
74125 2662
245771 8858
224783 7181
235656 4986
163114 3041
101632 1797
64682 4595
22763 4476
145956 9767
50440 3970
20831 9646
32979 365
147294 5959
5700 3518
167684 258
105791 2718
129850 8902
2168...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #28:

score: 0
Accepted
time: 643ms
memory: 20172kb

input:

250000 249999
233586 2024
249814 5609
98965 9482
21269 7996
112196 3685
56401 4243
248656 5822
246725 8874
239803 3997
154988 7106
163971 9153
17019 4804
114980 9267
15470 7944
148695 5822
48302 5830
17357 1357
85078 1597
217000 5941
193654 6835
41788 6310
84917 509
111123 2589
219424 5680
217784 85...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #29:

score: 0
Accepted
time: 633ms
memory: 18372kb

input:

100000 249999
218060 20345
27334 62482
125176 75231
164701 51166
191015 8172
197002 40902
212572 96076
79429 83748
8322 65763
117710 55688
163851 18354
61106 26868
169159 5528
85864 73608
229644 69531
69326 96862
136553 87015
41717 8087
3709 40727
233990 84886
99712 32178
217040 75596
149456 83736
1...

output:

1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
6.0
1.5
1.5
6.0
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
1.5
6.0
1.5
1.5
1.5
1.5
6.0
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
6.0
1.5
1.5
...

result:

ok 249999 numbers

Test #30:

score: 0
Accepted
time: 641ms
memory: 19112kb

input:

150000 249999
234931 117721
165760 121374
39901 90389
65401 36642
127661 143888
111190 11903
248547 55018
25670 51452
29737 77284
34785 88158
41023 86741
210736 96409
45042 131729
156818 38710
102234 58616
229573 45925
240495 63260
27301 13493
239464 120694
57130 18370
65373 113177
200234 111599
813...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
6.0
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #31:

score: 0
Accepted
time: 636ms
memory: 19524kb

input:

200000 249999
115119 166519
203638 63359
136662 96182
198943 18205
186741 173012
170532 142299
132543 22820
152237 171263
248127 46558
134531 159448
113450 155775
26555 131466
9868 37421
45419 144841
199395 140829
110924 34275
83572 11001
48496 65156
133341 100284
141543 60021
170546 6240
231712 152...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #32:

score: 0
Accepted
time: 672ms
memory: 20064kb

input:

250000 249999
81716 70790
72006 29146
86672 228636
88825 53682
198298 58728
197705 130597
169560 249058
143240 6263
156637 225375
177754 174622
67575 6866
139636 192494
53704 155110
8984 209943
65297 79914
153405 142122
225695 169949
96758 194754
245965 121739
212635 243505
234106 28727
242548 11416...

output:

1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
1.5
...

result:

ok 249999 numbers

Test #33:

score: 0
Accepted
time: 672ms
memory: 20160kb

input:

250000 249999
250000 1
249999 1
249998 2
249997 2
249996 3
249995 3
249994 4
249993 4
249992 5
249991 5
249990 6
249989 6
249988 7
249987 7
249986 8
249985 8
249984 9
249983 9
249982 10
249981 10
249980 11
249979 11
249978 12
249977 12
249976 13
249975 13
249974 14
249973 14
249972 15
249971 15
2499...

output:

1.5
1.5
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
6...

result:

ok 249999 numbers

Test #34:

score: 0
Accepted
time: 668ms
memory: 20120kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 2
249996 2
249995 2
249994 3
249993 3
249992 3
249991 4
249990 4
249989 4
249988 5
249987 5
249986 5
249985 6
249984 6
249983 6
249982 7
249981 7
249980 7
249979 8
249978 8
249977 8
249976 9
249975 9
249974 9
249973 10
249972 10
249971 10
249970 11
249...

output:

6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
6...

result:

ok 249999 numbers

Test #35:

score: 0
Accepted
time: 678ms
memory: 20160kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 1
249996 1
249995 2
249994 2
249993 2
249992 2
249991 2
249990 3
249989 3
249988 3
249987 3
249986 3
249985 4
249984 4
249983 4
249982 4
249981 4
249980 5
249979 5
249978 5
249977 5
249976 5
249975 6
249974 6
249973 6
249972 6
249971 6
249970 7
249969 ...

output:

6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
6...

result:

ok 249999 numbers

Test #36:

score: 0
Accepted
time: 662ms
memory: 20300kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 1
249996 1
249995 1
249994 1
249993 1
249992 1
249991 1
249990 1
249989 1
249988 1
249987 1
249986 1
249985 1
249984 1
249983 1
249982 1
249981 1
249980 1
249979 1
249978 1
249977 1
249976 1
249975 1
249974 1
249973 1
249972 1
249971 1
249970 1
249969 ...

output:

60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
...

result:

ok 249999 numbers

Test #37:

score: 0
Accepted
time: 674ms
memory: 20336kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 1
249996 1
249995 1
249994 1
249993 1
249992 1
249991 1
249990 1
249989 1
249988 1
249987 1
249986 1
249985 1
249984 1
249983 1
249982 1
249981 1
249980 1
249979 1
249978 1
249977 1
249976 1
249975 1
249974 1
249973 1
249972 1
249971 1
249970 1
249969 ...

output:

546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
...

result:

ok 249999 numbers

Test #38:

score: 0
Accepted
time: 696ms
memory: 20368kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 1
249996 1
249995 1
249994 1
249993 1
249992 1
249991 1
249990 1
249989 1
249988 1
249987 1
249986 1
249985 1
249984 1
249983 1
249982 1
249981 1
249980 1
249979 1
249978 1
249977 1
249976 1
249975 1
249974 1
249973 1
249972 1
249971 1
249970 1
249969 ...

output:

4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0...

result:

ok 249999 numbers

Test #39:

score: 0
Accepted
time: 719ms
memory: 20216kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 1
249996 1
249995 1
249994 1
249993 1
249992 1
249991 1
249990 1
249989 1
249988 1
249987 1
249986 1
249985 1
249984 1
249983 1
249982 1
249981 1
249980 1
249979 1
249978 1
249977 1
249976 1
249975 1
249974 1
249973 1
249972 1
249971 1
249970 1
249969 ...

output:

44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
4428...

result:

ok 249999 numbers

Test #40:

score: 0
Accepted
time: 719ms
memory: 20140kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 1
249996 1
249995 1
249994 1
249993 1
249992 1
249991 1
249990 1
249989 1
249988 1
249987 1
249986 1
249985 1
249984 1
249983 1
249982 1
249981 1
249980 1
249979 1
249978 1
249977 1
249976 1
249975 1
249974 1
249973 1
249972 1
249971 1
249970 1
249969 ...

output:

132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132...

result:

ok 249999 numbers

Test #41:

score: 0
Accepted
time: 321ms
memory: 11168kb

input:

100000 250000
100000 1
99999 1
99998 1
99997 1
99996 1
99995 1
99994 1
99993 1
99992 1
99991 1
99990 1
99989 1
99988 1
99987 1
99986 1
99985 1
99984 1
99983 1
99982 1
99981 1
99980 1
99979 1
99978 1
99977 1
99976 1
99975 1
99974 1
99973 1
99972 1
99971 1
99970 1
99969 1
99968 1
99967 1
99966 1
99965...

output:

14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
14761.5
1476...

result:

ok 250000 numbers

Test #42:

score: 0
Accepted
time: 663ms
memory: 20244kb

input:

250000 249999
250000 1
249999 1
249998 2
249997 2
249996 3
249995 3
249994 4
249993 4
249992 5
249991 5
249990 6
249989 6
249988 7
249987 7
249986 8
249985 8
249984 9
249983 9
249982 10
249981 10
249980 11
249979 11
249978 12
249977 12
249976 13
249975 13
249974 14
249973 14
249972 15
249971 15
2499...

output:

1.5
1.5
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
6...

result:

ok 249999 numbers

Test #43:

score: 0
Accepted
time: 650ms
memory: 20176kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 2
249996 2
249995 2
249994 3
249993 3
249992 3
249991 4
249990 4
249989 4
249988 5
249987 5
249986 5
249985 6
249984 6
249983 6
249982 7
249981 7
249980 7
249979 8
249978 8
249977 8
249976 9
249975 9
249974 9
249973 10
249972 10
249971 10
249970 11
249...

output:

6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
6...

result:

ok 249999 numbers

Test #44:

score: 0
Accepted
time: 713ms
memory: 20148kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 1
249996 1
249995 2
249994 2
249993 2
249992 2
249991 2
249990 3
249989 3
249988 3
249987 3
249986 3
249985 4
249984 4
249983 4
249982 4
249981 4
249980 5
249979 5
249978 5
249977 5
249976 5
249975 6
249974 6
249973 6
249972 6
249971 6
249970 7
249969 ...

output:

6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
6...

result:

ok 249999 numbers

Test #45:

score: 0
Accepted
time: 660ms
memory: 20156kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 1
249996 1
249995 1
249994 1
249993 1
249992 1
249991 1
249990 1
249989 1
249988 1
249987 1
249986 1
249985 1
249984 1
249983 1
249982 1
249981 1
249980 1
249979 1
249978 1
249977 1
249976 1
249975 1
249974 1
249973 1
249972 1
249971 1
249970 1
249969 ...

output:

60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
...

result:

ok 249999 numbers

Test #46:

score: 0
Accepted
time: 668ms
memory: 20112kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 1
249996 1
249995 1
249994 1
249993 1
249992 1
249991 1
249990 1
249989 1
249988 1
249987 1
249986 1
249985 1
249984 1
249983 1
249982 1
249981 1
249980 1
249979 1
249978 1
249977 1
249976 1
249975 1
249974 1
249973 1
249972 1
249971 1
249970 1
249969 ...

output:

546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
546.0
...

result:

ok 249999 numbers

Test #47:

score: 0
Accepted
time: 656ms
memory: 20396kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 1
249996 1
249995 1
249994 1
249993 1
249992 1
249991 1
249990 1
249989 1
249988 1
249987 1
249986 1
249985 1
249984 1
249983 1
249982 1
249981 1
249980 1
249979 1
249978 1
249977 1
249976 1
249975 1
249974 1
249973 1
249972 1
249971 1
249970 1
249969 ...

output:

4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0
4920.0...

result:

ok 249999 numbers

Test #48:

score: 0
Accepted
time: 663ms
memory: 20112kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 1
249996 1
249995 1
249994 1
249993 1
249992 1
249991 1
249990 1
249989 1
249988 1
249987 1
249986 1
249985 1
249984 1
249983 1
249982 1
249981 1
249980 1
249979 1
249978 1
249977 1
249976 1
249975 1
249974 1
249973 1
249972 1
249971 1
249970 1
249969 ...

output:

44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
44286.0
4428...

result:

ok 249999 numbers

Test #49:

score: 0
Accepted
time: 666ms
memory: 20240kb

input:

250000 249999
250000 1
249999 1
249998 1
249997 1
249996 1
249995 1
249994 1
249993 1
249992 1
249991 1
249990 1
249989 1
249988 1
249987 1
249986 1
249985 1
249984 1
249983 1
249982 1
249981 1
249980 1
249979 1
249978 1
249977 1
249976 1
249975 1
249974 1
249973 1
249972 1
249971 1
249970 1
249969 ...

output:

132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132859.5
132...

result:

ok 249999 numbers

Test #50:

score: 0
Accepted
time: 668ms
memory: 20064kb

input:

250000 250000
250000 1
249999 2
249998 2
249997 2
249996 2
249995 2
249994 2
249993 2
249992 2
249991 2
249990 2
249989 2
249988 2
249987 2
249986 2
249985 2
249984 2
249983 2
249982 2
249981 2
249980 2
249979 2
249978 2
249977 2
249976 2
249975 2
249974 2
249973 2
249972 2
249971 2
249970 2
249969 ...

output:

1.5
1.5
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
6.0
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
19.5
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
60.0
6...

result:

ok 250000 numbers

Extra Test:

score: -3
Extra Test Failed : Wrong Answer on 2
time: 0ms
memory: 4088kb

input:

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

output:

0
0
0
1.5
0
0
0
0
1.5
0

result:

wrong answer 2nd numbers differ - expected: '4.00000', found: '0.00000', error = '1.00000'