use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();

    let n: usize = it.next().unwrap().parse().unwrap();
    let q: usize = it.next().unwrap().parse().unwrap();

    let mut a: Vec<i64> = (0..n)
        .map(|_| it.next().unwrap().parse().unwrap())
        .collect();

    let sq = (n as f64).sqrt() as usize;
    let len = (n + sq - 1) / sq;

    let mut unit = vec![-1i64; len];
    let mut sum = vec![0i64; len];

    for b in 0..len {
        let mut one: i64 = -1;

        let l = b * sq;
        let r = std::cmp::min(n, l + sq);

        for j in l..r {
            if one == -1 {
                one = a[j];
            } else if one == a[j] {
            } else {
                one = -2;
            }
            sum[b] += a[j];
        }

        if one >= 0 {
            unit[b] = one;
        }
    }

    let mut answers = Vec::<i64>::new();

    for _ in 0..q {
        let typ: i32 = it.next().unwrap().parse().unwrap();

        if typ == 0 {
            let l: usize = it.next().unwrap().parse().unwrap();
            let r: usize = it.next().unwrap().parse().unwrap();

            let mut ans = 0i64;
            let mut now = l;

            while now < r && now % sq != 0 {
                if unit[now / sq] != -1 {
                    ans += unit[now / sq];
                } else {
                    ans += a[now];
                }
                now += 1;
            }

            while now < r && now + sq < r {
                ans += sum[now / sq];
                now += sq;
            }

            while now < r {
                if unit[now / sq] != -1 {
                    ans += unit[now / sq];
                } else {
                    ans += a[now];
                }
                now += 1;
            }

            answers.push(ans);
        } else if typ == 1 {
            let l: usize = it.next().unwrap().parse().unwrap();
            let r: usize = it.next().unwrap().parse().unwrap();
            let x: i64 = it.next().unwrap().parse().unwrap();

            let mut now = l;

            while now < r && now % sq != 0 {
                let b = now / sq;

                if unit[b] != -1 {
                    let ume = unit[b];
                    unit[b] = -1;
                    sum[b] = 0;

                    let bl = b * sq;
                    let br = std::cmp::min(n, bl + sq);

                    for i in bl..br {
                        a[i] = ume;
                        sum[b] += a[i];
                    }
                }

                sum[b] -= a[now];
                a[now] = x;
                sum[b] += a[now];

                now += 1;
            }

            while now < r && now + sq < r {
                let b = now / sq;
                unit[b] = x;
                sum[b] = x * sq as i64;
                now += sq;
            }

            while now < r {
                let b = now / sq;

                if unit[b] != -1 {
                    let ume = unit[b];
                    unit[b] = -1;
                    sum[b] = 0;

                    let bl = b * sq;
                    let br = std::cmp::min(n, bl + sq);

                    for i in bl..br {
                        a[i] = ume;
                        sum[b] += a[i];
                    }
                }

                sum[b] -= a[now];
                a[now] = x;
                sum[b] += a[now];

                now += 1;
            }
        } else {
            let l: usize = it.next().unwrap().parse().unwrap();
            let r: usize = it.next().unwrap().parse().unwrap();

            let mut now = l;

            while now < r && now % sq != 0 {
                let b = now / sq;

                if unit[b] != -1 {
                    let ume = unit[b];
                    unit[b] = -1;
                    sum[b] = 0;

                    let bl = b * sq;
                    let br = std::cmp::min(n, bl + sq);

                    for i in bl..br {
                        a[i] = ume;
                        sum[b] += a[i];
                    }
                }

                sum[b] -= a[now];
                a[now] = (a[now] as f64).sqrt() as i64;
                sum[b] += a[now];

                now += 1;
            }

            while now < r && now + sq < r {
                let b = now / sq;

                if unit[b] != -1 {
                    let ume = (unit[b] as f64).sqrt() as i64;
                    unit[b] = ume;
                    sum[b] = ume * sq as i64;
                    now += sq;
                } else {
                    let mut one = -1i64;
                    sum[b] = 0;

                    for i in now..now + sq {
                        a[i] = (a[i] as f64).sqrt() as i64;
                        sum[b] += a[i];

                        if one == -1 {
                            one = a[i];
                        } else if one == a[i] {
                        } else {
                            one = -2;
                        }
                    }

                    if one >= 0 {
                        unit[b] = one;
                        sum[b] = one * sq as i64;
                    }

                    now += sq;
                }
            }

            while now < r {
                let b = now / sq;

                if unit[b] != -1 {
                    let ume = unit[b];
                    unit[b] = -1;
                    sum[b] = 0;

                    let bl = b * sq;
                    let br = std::cmp::min(n, bl + sq);

                    for i in bl..br {
                        a[i] = ume;
                        sum[b] += a[i];
                    }
                }

                sum[b] -= a[now];
                a[now] = (a[now] as f64).sqrt() as i64;
                sum[b] += a[now];

                now += 1;
            }
        }
    }

    let mut out = String::new();
    for v in answers {
        out.push_str(&format!("{}\n", v));
    }
    print!("{}", out);
}