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
        }
    }
}