My .conkyrc

use_spacer right
use_xft yes
font Microsoft YaHei:size=8
xftfont Microsoft YaHei:size=8
override_utf8_locale yes
update_interval 1.0
own_window yes
own_window_type desktop
own_window_transparent yes
#own_window_hints undecorated,below,sticky,skip_taskbar,skip_pager
own_window_argb_visual yes
own_window_argb_value 120
double_buffer yes
minimum_size 206 5
maximum_width 400
draw_shades yes
draw_outline no
draw_borders no
draw_graph_borders no
default_color ffffff
default_shade_color 000000
default_outline_color 000000
alignment top_right
gap_x 5
gap_y 35
cpu_avg_samples 2
uppercase no # set to yes if you want all text to be in uppercase

TEXT
${font Microsoft YaHei:style=Bold:pixelsize=22}${alignc}${time %H:%M:%S}
${font Microsoft YaHei:pixelsize=16}${alignc}${time %b%d日星期%a}${alignc}
${color #ffa200}${hr 2}
${font Microsoft YaHei:pixelsize=12}
${color #00ffcf}主机名:${color #00ffcf} $alignr$nodename
${color #00ffcf}内核: ${color #00ffcf}$alignr$kernel
${color #00ffcf}已运行时间: ${color #00ffcf}$alignr$uptime
${color #ffd700}${stippled_hr 1}
${font Microsoft YaHei:pixelsize=12}
${color #00ff1e}CPU 0: ${cpu cpu0}% $alignr$acpitemp°C(T)
${color #dcff82}${cpubar 8 cpu0}
${color #00ff1e}CPU 1: ${cpu cpu1}% 
${color #dcff82}${cpubar 8 cpu1}
${color #00ff1e}CPU占用:$alignr CPU%
${color #ddaa00} ${top name 1}$alignr${top cpu 1}
${color lightgrey} ${top name 2}$alignr${top cpu 2}
${color lightgrey} ${top name 3}$alignr${top cpu 3}
${color #ffd700}${stippled_hr 1}$color
${font Microsoft YaHei:pixelsize=12}
${color #00ff1e}SAM: $mem $alignr${color #db7093}$memperc%
${color #78af78}${membar 8}
${color #00ff1e}SWAP: $swap $alignr ${color #db7093}$swapperc%
${color #78af78}${swapbar 8}
${color #00ff1e}内存占用: $alignr MEM% 
${color #ddaa00} ${top_mem name 1}$alignr ${top_mem mem 1}
${color lightgrey} ${top_mem name 2}$alignr ${top_mem mem 2}
${color lightgrey} ${top_mem name 3}$alignr ${top_mem mem 3}
${color #ffd700}${stippled_hr 1}$color
${font Microsoft YaHei:pixelsize=12}
${color #00ff1e}硬盘读取速度:${alignr}${diskio_read}
${color #00ff1e}硬盘写入速度:${alignr}${diskio_write}
${color #ffd700}${stippled_hr 1}$color
${font Microsoft YaHei:pixelsize=12}
${color #00ff1e}网络 $alignr ${color #00ff1e}IP地址: ${color DDAA00}${addr enp3s0}
${voffset 1}${color #98c2c7} 上传: ${color #db7093}${upspeed enp3s0}/s ${alignr}${color #98c2c7}总共: ${color #db7093}${totalup enp3s0}
${voffset 1}${color #98c2c7} 下载: ${color #ddaa00}${downspeed enp3s0}/s ${alignr}${color #98c2c7}总共: ${color #ddaa00}${totaldown enp3s0}
${font Microsoft YaHei:pixelsize=12}
${color #ffa200}${hr 2}

Arpa and a Game with Mojtaba

题目描述

Mojtaba and Arpa are playing a game. They have a list of $n$ numbers in the game.
In a player’s turn, he chooses a number $p^k$ (where $p$ is a prime number and $k$ is a positive integer) such that $p^k$ divides at least one number in the list. For each number in the list divisible by $p^k$, call it $x$, the player will delete $x$ and add ${x \over p^k}$ to the list. The player who can not make a valid choice of $p$ and $k$ loses.
Mojtaba starts the game and the players alternatively make moves. Determine which one of players will be the winner if both players play optimally.

算法分析

给定一个长度为$n$的序列,两人轮流进行操作,每次操作给定$p, k$,其中$p$是素数,$k$是正整数,将序列中所有能被$p^k$整除的数除以$p^k$(要求至少有一个数能被整除),不能进行操作的人算输。问在两人都采取最优策略的情况下,先手必胜还是后手必胜。
数据范围:$1 \le n \le 100, \; 1 \le a_i \le 10^9$。

算法分析

考虑某个质数$p$,它对其他质数不产生任何影响,因此可以分别处理每个质数。
设处理到的质数是$p$,我们计算出它在序列每个数中的最高次数,并储存在二进制数s中。那么在进行一次$p, k$操作后,s会被更新成(s>>k)|(s&((1<<(k-1))-1))。把s看成点,操作看成边,就构成了一张有向图。分别计算每个质数有向图的SG函数,异或起来,如果等于$0$则后手必胜,否则先手必胜。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

namespace std {
  template <typename T>
  void maxify(T &a, T b) { b > a && (a = b); }
  template <typename T>
  void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline IOManager operator > (T &x) {
    read(x); return *this;
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char c) {
    putchar(c);
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
  template <typename T>
  inline IOManager operator < (T x) {
    write(x); return *this;
  }
} io;

struct Solver {
private:
  static const int N = 100;
  int n, a[N + 1];
  map <int, int> sg, num;
  void input() {
    io > n;
    for (int i = 1; i <= n; ++ i) io > a[i];
  }
  void init() {
    for (int i = 1; i <= n; ++ i)
      if (a[i] > 1) {
        int q = sqrt(a[i]);
        for (int j = 2; j <= q; ++ j) {
          if (a[i] == 1) break;
          if (! (a[i] % j)) {
            int cnt = 0;
            while (! (a[i] % j)) a[i] /= j, ++ cnt;
            num[j] |= 1 << cnt - 1;
          }
        }
        if (a[i] > 1) num[a[i]] |= 1;
      }
  }
  int get_sg(int t) {
    if (! t) return 0;
    if (sg.count(t)) return sg[t];
    map <int, bool> vis;
    int p = t, cnt = 0;
    while (p) p >>= 1, ++ cnt;
    for (int i = 1; i <= cnt; ++ i)
      vis[get_sg((t >> i) | (t & (1 << i - 1) - 1))] = true;
    cnt = 0;
    while (vis[cnt]) ++ cnt;
    return sg[t] = cnt;
  }
  void process() {
    int ans = 0;
    for (map <int, int> :: iterator it = num.begin(); it != num.end(); ++ it) ans ^= get_sg(it->second);
    if (! ans) io < (char *) "Arpa\n";
    else io < (char *) "Mojtaba\n";
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

Arpa and a List of Numbers

题目描述

Arpa has found a list containing $n$ numbers. He calls a list bad if and only if it is not empty and gcd of numbers in the list is $1$.
Arpa can perform two types of operations:

  • Choose a number and delete it with cost $x$.
  • Choose a number and increase it by $1$ with cost $y$.

Arpa can apply these operations to as many numbers as he wishes, and he is allowed to apply the second operation arbitrarily many times on the same number.
Help Arpa to find the minimum possible cost to make the list good.

题意概述

给定一个长度为$n$的序列,第$i$个数字为$a_i$。有两种操作:删除一个数,消耗$x$;将一个数加$1$,消耗$y$。求使得序列中所有数的最大公约数大于$1$的最少消耗。
数据范围:$1 \le n \le 5 \times 10^5, \; 1 \le x, y \le 10^9, \; 1 \le a_i \le 10^6$。

算法分析

枚举$[2, 10^6]$中的素数$p$作为最大公约数(合数作为最大公约数的消耗一定不比质数少)。对于序列中的每个数,要么将它删去,要么将它变成不小于它且最小的$p$的倍数。设$d_i=\left\lceil {a_i \over p} \right\rceil \times p -a_i$。显然,若$x \le d_i \times y$,那么将它删去更优,否则将它变成$p$的倍数更优。也就是说,对于$d_i \ge {x \over y}$的数,我们将它删去,否则将它变成$p$的倍数。预处理出前缀和,根据调和级数,可知时间复杂度为$O(a_i\log a_i)$。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

void minify(long long &a, long long b) { b < a && (a = b); }

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline IOManager operator > (T &x) {
    read(x); return *this;
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char c) {
    putchar(c);
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
  template <typename T>
  inline IOManager operator < (T x) {
    write(x); return *this;
  }
} io;

struct Solver {
private:
  static const int N = 1000000;
  static const int M = 1000000;
  int n, x, y, a[N + 1], cnt[N + 1 << 1];
  long long sum[N + 1 << 1];
  int top, prime[N];
  bool vis[N + 1 << 1];
  void input() {
    io > n > x > y;
    for (int i = 1; i <= n; ++ i) io > a[i], ++ cnt[a[i]], sum[a[i]] += a[i];
  }
  void init() {
    for (int i = 1; i <= M << 1; ++ i) cnt[i] += cnt[i - 1], sum[i] += sum[i - 1];
    for (int i = 2; i <= M; ++ i) {
      if (! vis[i]) prime[++ top] = i;
      for (int j = 1; j <= top && i * prime[j] <= M; ++ j) {
        vis[i * prime[j]] = true;
        if (! (i % prime[j])) break;
      }
    }
  }
  void process() {
    int p = x / y;
    long long ans = 1000000000000000000ll;;
    for (int i = 1; i <= top; ++ i) {
      long long tmp = 0;
      int delta = prime[i] - p - 1;
      for (int j = 0; j <= N; j += prime[i]) {
        if (delta < 0) {
          tmp += (((long long) cnt[j + prime[i]] - cnt[j]) * (j + prime[i]) - (sum[j + prime[i]] - sum[j])) * y;
        } else {
          tmp += ((long long) cnt[j + delta] - cnt[j]) * x + (((long long) cnt[j + prime[i]] - cnt[j + delta]) * (j + prime[i]) - (sum[j + prime[i]] - sum[j + delta])) * y;
        }
      }
      minify(ans, tmp);
    }
    io < ans < '\n';
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

Goodbye Souvenir

题目描述

I won’t feel lonely, nor will I be sorrowful… not before everything is buried.
A string of $n$ beads is left as the message of leaving. The beads are numbered from $1$ to $n$ from left to right, each having a shape numbered by integers between $1$ and $n$ inclusive. Some beads may have the same shapes.
The memory of a shape $x$ in a certain subsegment of beads, is defined to be the difference between the last position and the first position that shape $x$ appears in the segment. The memory of a subsegment is the sum of memories over all shapes that occur in it.
From time to time, shapes of beads change as well as the memories. Sometimes, the past secreted in subsegments are being recalled, and you are to find the memory for each of them.

题意概述

给定一个长度为$n$的序列$a_i$,有$m$次操作。操作有两种:给定$p, x$,将第$p$个数修改成$x$;给定$l, r$,求$[l, r]$内每种数字的长度之和。某种数字长度的定义是该数字在区间内第一次出现的位置与最后一次出现的位置之差。
数据范围:$1 \le n, m \le 10^5, \; 1 \le a_i, x \le n$。

算法分析

设区间$[l, r]$中某种数字出现的位置为$p_1, p_2, \ldots, p_k$,显然这个数字对答案的贡献为$p_k-p_1=(p_2-p_1)+(p_3-p_2)+ \cdots +(p_k-p_{k-1})$。令$pre_i$表示在$i$之前离$i$最近的等于$a_i$的数的位置,那么贡献就是$(p_2-pre_2)+(p_3-pre_3)+ \cdots +(p_k-pre_k)$。我们把每个数$a_i$想像成二维空间中的一个点$(pre_i, i)$,它的权值是$i-pre_i$。那么问题就变成了求在矩形$(l, l)-(r, r)$中的点权之和。这可以用传说中的CDQ分治来解决。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>

#define int long long

using namespace std;

void maxify(int &a, int b) { b > a && (a = b); }
void minify(int &a, int b) { b < a && (a = b); }

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline IOManager operator > (T &x) {
    read(x); return *this;
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char c) {
    putchar(c);
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
  template <typename T>
  inline IOManager operator < (T x) {
    write(x); return *this;
  }
} io;

struct BinaryIndexedTree {
private:
  static const int N = 200000;
  int n, a[N];

public:
  void init(int t) {
    n = t, memset(a, 0, sizeof a);
  }
  void add(int p, int v) {
    for (; p <= n; p += p & -p) a[p] += v;
  }
  int get(int p) {
    int ret = 0;
    for (; p; p -= p & -p) ret += a[p];
    return ret;
  }
};

struct Set {
private:
  static const int N = 200000;
  int a[N];
  set <int> s[N];
  set <int> :: iterator it;

public:
  void modify(int p, int v) {
    if (a[p]) s[a[p]].erase(p);
    a[p] = v;
    s[a[p]].insert(p);
  }
  int prev(int p) {
    it = s[a[p]].find(p);
    return it == s[a[p]].begin() ? *it : *(-- it);
  }
  int next(int p) {
    it = ++ s[a[p]].find(p);
    return it == s[a[p]].end() ? *(-- it) : *it;
  }
};

#define MODIFY 1
#define QUERY 2

struct Solver {
private:
  static const int N = 200000;
  int n, m, numq, top, pos[N], pre[N], ans[N];
  BinaryIndexedTree tree;
  Set s;
  struct Query {
    int type, x, y, w, id;
    bool operator < (const Query &q) const {
      return x == q.x ? type < q.type : x < q.x;
    }
  } q[N << 2], tmp[N << 2];
  void add_query(int type, int x, int y, int w, int id) {
    q[++ numq] = (Query) { type, x, y, w, id };
  } 
  void input() {
    io > n > m;
    for (int i = 2; i <= n + 1; ++ i) {
      int t; io > t, s.modify(i, t);
      int prev = s.prev(i);
      add_query(MODIFY, prev, i, i - prev, 0);
    }
    for (int i = 1; i <= m; ++ i) {
      int o; io > o;
      if (o == 1) {
        int p, x; io > p > x; ++ p;
        int prev = s.prev(p), next = s.next(p);
        if (prev < p) add_query(MODIFY, prev, p, prev - p, 0);
        if (next > p) add_query(MODIFY, p, next, p - next, 0);
        if (prev < p && next > p) add_query(MODIFY, prev, next, next - prev, 0);
        s.modify(p, x);
        prev = s.prev(p), next = s.next(p);
        if (prev < p && next > p) add_query(MODIFY, prev, next, prev - next, 0);
        if (prev < p) add_query(MODIFY, prev, p, p - prev, 0);
        if (next > p) add_query(MODIFY, p, next, next - p, 0);
      } else {
        int l, r; io > l > r, ++ l, ++ r, ++ top;
        add_query(QUERY, r, r, 1, top);
        add_query(QUERY, r, l - 1, -1, top);
        add_query(QUERY, l - 1, r, -1, top);
        add_query(QUERY, l - 1, l - 1, 1, top);
      }
    }
  }
  void process(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    process(l, mid), process(mid + 1, r);
    int s = l, t = mid + 1, pnt = l;
    while (s <= mid && t <= r) {
      if (q[s] < q[t]) {
        if (q[s].type == MODIFY) tree.add(q[s].y, q[s].w);
        tmp[pnt ++] = q[s ++];
      } else {
        if (q[t].type == QUERY) ans[q[t].id] += q[t].w * tree.get(q[t].y);
        tmp[pnt ++] = q[t ++];
      }
    }
    while (t <= r) {
      if (q[t].type == QUERY) ans[q[t].id] += q[t].w * tree.get(q[t].y);
      tmp[pnt ++] = q[t ++];
    }
    for (int i = l; i < s; ++ i) if (q[i].type == MODIFY) tree.add(q[i].y, -q[i].w);
    while (s <= mid) tmp[pnt ++] = q[s ++];
    for (int i = l; i <= r; ++ i) q[i] = tmp[i];
  }

public:
  void solve() {
    input(), tree.init(n + 1), process(1, numq);
    for (int i = 1; i <= top; ++ i) io < ans[i] < '\n';
  }
} solver;

signed main() {
  solver.solve();
  return 0;
}

Destiny

题目描述

Once, Leha found in the left pocket an array consisting of $n$ integers, and in the right pocket $q$ queries of the form $l$ $r$ $k$. If there are queries, then they must be answered. Answer for the query is minimal $x$ such that $x$ occurs in the interval $l$ $r$ strictly more than ${r-l+1 \over k}$ times or $-1$ if there is no such number. Help Leha with such a difficult task.

题意概述

给定包含$n$个数的序列,有$q$次询问,每次询问给定$l, r, k$,求区间$[l, r]$中出现次数严格大于${r-l+1 \over k}$的最小数字。
数据范围:$1 \le n, q \le 3 \times 10^5, \; 1 \le a_i \le n, \; 2 \le k \le 5$。

算法分析

建主席树,第$i$个位置上的线段树是前$i$个数的权值线段树。这样就可以用前缀和思想快速求出区间$[l, r]$中某个数出现的次数。对于每个询问,用第$r$个位置上线段树的值减去第$(l-1)$个位置上线段树的值,直接在主席树上暴力查找。由于$k$比较小,查找复杂度不会太高。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline IOManager r(T &x) {
    read(x); return *this;
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char c) {
    putchar(c);
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
  template <typename T>
  inline IOManager w(T x) {
    write(x); return *this;
  }
} io;

struct SegmentTree {
private:
  static const int N = 9000000;
  int tot;
  struct Node {
    int val, child[2];
  } node[N];
  int add_point(int root, int l, int r, int p) {
    if (l == r) {
      node[++ tot] = (Node) { node[root].val, 0, 0 };
      ++ node[tot].val; return tot;
    }
    int mid = l + r >> 1, rec = ++ tot;
    node[rec] = (Node) { 0, 0, 0 };
    if (p <= mid) {
      node[rec].child[1] = node[root].child[1];
      node[rec].child[0] = add_point(node[root].child[0], l, mid, p);
    } else {
      node[rec].child[0] = node[root].child[0];
      node[rec].child[1] = add_point(node[root].child[1], mid + 1, r, p);
    }
    node[rec].val = node[node[rec].child[0]].val + node[node[rec].child[1]].val;
    return rec;
  }
  int query_point(int root1, int root2, int l, int r, int p) {
    if (node[root2].val - node[root1].val < p) return -1;
    if (l == r) return node[root2].val - node[root1].val >= p ? l : -1;
    int mid = l + r >> 1, res = -1;
    if (node[node[root2].child[0]].val - node[node[root1].child[0]].val >= p)
      res = query_point(node[root1].child[0], node[root2].child[0], l, mid, p);
    if (~ res) return res;
    res = query_point(node[root1].child[1], node[root2].child[1], mid + 1, r, p);
    return res;
  }

public:
  int n, cnt, root[N];
  void add(int p) {
    root[cnt + 1] = add_point(root[cnt], 1, n, p), ++ cnt;
  }
  int find(int l, int r, int p) {
    return query_point(root[l - 1], root[r], 1, n, p);
  }
  void print() {
    cout << cnt << endl;
    for (int i = 1; i <= cnt; ++ i) cout << root[i] << ' ';
    cout << endl << tot << endl;
    for (int i = 1; i <= tot; ++ i) cout << i << ' ' << node[i].val << ' ' << node[i].child[0] << ' ' << node[i].child[1] << endl;
  }
};

struct Solver {
private:
  int n, q;
  SegmentTree tree;
  void input() {
    io.r(n).r(q);
    tree.n = n;
    for (int i = 1; i <= n; ++ i) {
      int t; io.read(t), tree.add(t);
    }
  }
  void process() {
    int l, r, k; io.r(l).r(r).r(k);
    int p = (r - l + 1) / k + 1;
    io.w(tree.find(l, r, p)).w('\n');
  }

public:
  void solve() {
    input(); while (q --) process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}