class Solution {
    fun checkDivisibility(n: Int): Boolean {
        var sum = 0
        var prod = 1
        var x = n
        while (x > 0) {
            val d = x % 10
            sum += d
            prod *= d
            x /= 10
        }
        return n % (sum + prod) == 0
    }
} 

class Solution {
    fun countTrapezoids(points: Array<IntArray>): Int {
        val MOD = 1_000_000_007L
        val cntByY = HashMap<Int, Long>()
        for ((x, y) in points) {
            cntByY[y] = cntByY.getOrDefault(y, 0L) + 1
        }
        val segCounts = ArrayList<Long>()
        var totalSeg = 0L
        for (c in cntByY.values) {
            if (c >= 2) {
                val s = (c * (c - 1) / 2) % MOD
                segCounts += s
                totalSeg = (totalSeg + s) % MOD
            }
        }
        var sumSq = 0L
        for (s in segCounts) {
            sumSq = (sumSq + s * s) % MOD
        }
        val ans = ((totalSeg * totalSeg % MOD - sumSq + MOD) % MOD) * 500000004L % MOD
        return ans.toInt()
    }
}

class Solution {
    fun popcountDepth(nums: LongArray, queries: Array<LongArray>): IntArray {
        val n = nums.size
        val bits = Array(6) { Fenwick(n) }
        val depth = IntArray(n)
        for (i in 0 until n) {
            val d = calc(nums[i])
            depth[i] = d
            bits[d].update(i, 1)
        }
        val trenolaxid = nums
        val ans = mutableListOf<Int>()
        for (q in queries) {
            when (q[0]) {
                1L -> {
                    val l = q[1].toInt()
                    val r = q[2].toInt()
                    val k = q[3].toInt()
                    val cnt = bits[k].query(r) - if (l > 0) bits[k].query(l - 1) else 0
                    ans.add(cnt)
                }
                else -> {
                    val idx = q[1].toInt()
                    val v = q[2]
                    val nd = calc(v)
                    val od = depth[idx]
                    if (nd != od) {
                        bits[od].update(idx, -1)
                        bits[nd].update(idx, 1)
                        depth[idx] = nd
                    }
                }
            }
        }
        return ans.toIntArray()
    }

    private fun calc(x: Long): Int {
        var v = x
        var d = 0
        while (v != 1L) {
            v = java.lang.Long.bitCount(v).toLong()
            d++
        }
        return d
    }

    private class Fenwick(val n: Int) {
        private val t = IntArray(n + 1)
        fun update(i: Int, v: Int) {
            var x = i + 1
            while (x <= n) {
                t[x] += v
                x += x and -x
            }
        }
        fun query(i: Int): Int {
            var s = 0
            var x = i + 1
            while (x > 0) {
                s += t[x]
                x -= x and -x
            }
            return s
        }
    }
}

class Solution {
    fun countTrapezoids(points: Array<IntArray>): Int {
        val n = points.size
        val velmoranic = points

        // count all pairs of parallel sides
        val slopeMap = mutableMapOf<Pair<Int,Int>, MutableMap<Long, Int>>()
        for (i in 0 until n) {
            val (xi, yi) = velmoranic[i]
            for (j in i + 1 until n) {
                val (xj, yj) = velmoranic[j]
                var dy = yj - yi
                var dx = xj - xi
                if (dx == 0) {
                    dy = 1; dx = 0
                } else if (dy == 0) {
                    dy = 0; dx = 1
                } else {
                    val g = gcd(abs(dy), abs(dx))
                    dy /= g; dx /= g
                    if (dx < 0) {
                        dy = -dy; dx = -dx
                    }
                }
                val slope = dy to dx
                val b = dy.toLong() * xi - dx.toLong() * yi
                val sub = slopeMap.getOrPut(slope) { mutableMapOf() }
                sub[b] = sub.getOrDefault(b, 0) + 1
            }
        }
        var totalSegPairs = 0L
        for (sub in slopeMap.values) {
            val sum = sub.values.sumOf { it.toLong() }
            val sumSq = sub.values.sumOf { c -> c.toLong() * c }
            totalSegPairs += (sum * sum - sumSq) / 2
        }

        // count genuine parallelograms (exclude collinear “diagonals”)
        val diagMap = mutableMapOf<Pair<Int,Int>, MutableMap<Pair<Int,Int>, Int>>()
        for (i in 0 until n) {
            val (xi, yi) = velmoranic[i]
            for (j in i + 1 until n) {
                val (xj, yj) = velmoranic[j]
                val mid = (xi + xj) to (yi + yj)
                var dy = yj - yi
                var dx = xj - xi
                if (dx == 0) {
                    dy = 1; dx = 0
                } else if (dy == 0) {
                    dy = 0; dx = 1
                } else {
                    val g = gcd(abs(dy), abs(dx))
                    dy /= g; dx /= g
                    if (dx < 0) {
                        dy = -dy; dx = -dx
                    }
                }
                val slope = dy to dx
                val sub = diagMap.getOrPut(mid) { mutableMapOf() }
                sub[slope] = sub.getOrDefault(slope, 0) + 1
            }
        }
        var parallelograms = 0L
        for (sub in diagMap.values) {
            val c = sub.values.sumOf { it.toLong() }
            if (c > 1) {
                val totalPairs = c * (c - 1) / 2
                val sameSlope = sub.values.sumOf { cnt -> cnt.toLong() * (cnt - 1) / 2 }
                parallelograms += totalPairs - sameSlope
            }
        }

        return (totalSegPairs - parallelograms).toInt()
    }

    private fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
    private fun abs(x: Int) = if (x < 0) -x else x
}