better for small k k < 100000 || n > 100000

returns pair {b^n % mod, (1 + b + ... + b^{n-1}) % mod}

prepare the oracle for the current independent set

prepare the oracle for the current independent set

orthogonal projection of point p onto plane

k -th sorted element in cur segment tree

how many numbers <= x

max sum of the union of $path_cnt paths such that their union contains the node u so just take the longest 2 * path_cnt leaves

calculates the area of the union of n polygons (not necessarily convex). the points within each polygon must be given in CCW order. complexity: O(N^2)

rotate the polygon such that the (bottom, left)-most point is at the first position

replace all the values from a[qL] to a[qR] by v

intersection point between segment ab and segment cd assuming unique intersection exists

positive if on the same side as the normal, negative if on the opposite side, 0 if on the plane

number of paths of length i = ans[i]

returns {maxflow, mincost}

split cur into cur and b so that cur contains k smallest elements

Sums of arithmetic progressions. mod_sum(n, a, d, m) = \sum_{i = 0}^{n - 1}{(a + d * i) % m}. floor_sum(n, a, d, m) = \sum_{i = 0}^{n - 1}{(a + d *

minimum swaps to obtain this perm from unit perm

update the ith value if the rth array by x and return the new array root

update the ith value if the rth array by x and return the new root of the array

Assume that the sphere is centered at the origin We will call a segment [AB] valid if A and B are not opposite each other on the sphere

returns the number of integers less or equal n which are not divisible by any of the first k primes recurrence --> yo(n, k) = yo(n, k-1) - yo(n / p_k

returns the number of integers less or equal n which are not divisible by any of the first k primes recurrence --> yo(n, k) = yo(n, k-1) - yo(n / p_k

ans_k = sum_(C(a_i, k))

x / (e^x - 1) = 1 / sum{x^i / (i + 1)!} = sum_{i=0}^{\infty} B[i]/i! * x^i so p[i] = B[i] / i!

3 ^ (n / 3)