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

fn main() {
    let mut s = String::new();
    io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.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![-1_i64; len];
    let mut sum = vec![0_i64; len];
    let mut one_or_zero = vec![0_i32; len];

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

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

        for j in l..r {
            if a[j] >= 2 {
                oneflag = 0;
            }

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

            sum[b] += a[j];
        }

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

        one_or_zero[b] = oneflag;
    }

    let mut answers: Vec<i64> = Vec::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 = 0_i64;
            let mut now = l;

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

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

            while now < r {
                let b = now / sq;
                if unit[b] != -1 {
                    ans += unit[b];
                } 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];
                    }
                }

                if x >= 2 {
                    one_or_zero[b] = 0;
                }

                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;

                if x <= 1 {
                    one_or_zero[b] = 1;
                } else {
                    one_or_zero[b] = 0;
                }

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

                if x >= 2 {
                    one_or_zero[b] = 0;
                }

                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 one_or_zero[b] == 1 {
                    now += sq;
                } else 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: i64 = -1;
                    sum[b] = 0;
                    let mut oneflag = 1;

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

                        if a[i] >= 2 {
                            oneflag = 0;
                        }

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

                    one_or_zero[b] = oneflag;

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