1 /**************************************************************  2     Problem: 3570  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:2284 ms  7     Memory:6288 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cmath> 12   13 using namespace std; 14 typedef long long ll; 15 typedef double lf; 16 const lf A = 0.8; 17 const int N = 200005; 18   19 int n, C; 20 int size[N], son[N][2], val[N], f[N], tot, root; 21 int data[N], id[N], cnt; 22   23 inline int read() { 24     int x = 0; 25     char ch = getchar(); 26     while (ch < ‘0‘ || ‘9‘ < ch) 27         ch = getchar(); 28     while (‘0‘ <= ch && ch <= ‘9‘) { 29         x = x * 10 + ch - ‘0‘; 30         ch = getchar(); 31     } 32     return x; 33 } 34   35 int ins(int x, int p) { 36     ++size[x]; 37     int S = p >= val[x]; 38     if (!son[x][S]) { 39         son[x][S] = ++tot; 40         f[tot] = x, size[tot] = 1, val[tot] = p; 41         return tot; 42     }else return ins(son[x][S], p); 43 } 44   45 int build(int fa, int l, int r) { 46     int mid = l + r >> 1, x = id[mid]; 47     f[x] = fa, son[x][0] = son[x][1] = 0, size[x] = 1; 48     val[x] = data[mid]; 49     if (l == r) return x; 50     if (l < mid) size[x] += size[son[x][0] = build(x, l, mid - 1)]; 51     if (mid < r) size[x] += size[son[x][1] = build(x, mid + 1, r)]; 52     return x; 53 } 54   55 void dfs(int x) { 56     if (son[x][0]) dfs(son[x][0]); 57     data[++cnt] = val[x], id[cnt] = x; 58     if (son[x][1]) dfs(son[x][1]); 59 } 60   61 inline int rebuild(int x) { 62     cnt = 0; 63     dfs(x); 64     return build(f[x], 1, cnt); 65 } 66   67 inline void insert(int p) { 68     if (!root) { 69         root = tot = size[1] = 1; 70         val[1] = p; 71         return; 72     } 73     int x = ins(root, p), dep = 0, z = x; 74     while (f[z]) z = f[z], ++dep; 75     if (dep < log(tot) / log(1 / A)) return; 76     while ((lf) size[son[x][0]] < A * size[x] && (lf)size[son[x][1]] < A * size[x]) 77         x = f[x]; 78     if (!x) return; 79     if (x == root) { 80         root = rebuild(x); 81         return; 82     } 83     int y = f[x], S = son[y][1] == x; 84     son[y][S] = rebuild(x); 85 } 86   87 inline int find_kth(int k) { 88     int x = root, sum; 89     while (1) { 90         sum = size[son[x][0]] + 1; 91         if (k == sum) return val[x]; 92         if (k < sum) x = son[x][0]; 93         else k -= sum, x = son[x][1]; 94     } 95 } 96   97 int main() { 98     int x, y, z; 99     n = read(), C = read();100     while (n--) {101         x = read(), read(), read();102         insert(x);103     }104     n = read();105     while (n--) {106         x = read();107         if (x) {108             y = read(), z = find_kth(read());109             printf("%.3lf\n", sqrt((ll) 2 * C * y + (ll) z * z));110         } else111             insert(read()), read(), read();112     }113     return 0;114 }