package main

import (
	"io"
	"math/bits"
	"os"
	"strconv"
)

const MOD int64 = 998244353

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n && (fs.data[fs.idx] < '0' || fs.data[fs.idx] > '9') {
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n {
		b := fs.data[fs.idx]
		if b < '0' || b > '9' {
			break
		}
		val = val*10 + int(b-'0')
		fs.idx++
	}
	return val
}

func main() {
	fs := NewFastScanner()
	n := fs.NextInt()
	q := fs.NextInt()

	a := make([]uint8, n+1)
	for i := 1; i <= n; i++ {
		a[i] = uint8(fs.NextInt())
	}

	stride := n + 1

	valPref := make([]uint32, 51*stride)
	var valBase [51]int
	for v := 0; v <= 50; v++ {
		base := v * stride
		valBase[v] = base
		var cur uint32
		vv := uint8(v)
		for i := 1; i <= n; i++ {
			if a[i] == vv {
				cur++
			}
			valPref[base+i] = cur
		}
	}

	var parity [64][51]uint8
	for s := 1; s < 64; s++ {
		for v := 0; v <= 50; v++ {
			if bits.OnesCount8(uint8(s&v))&1 == 1 {
				parity[s][v] = 1
			}
		}
	}

	maskPref := make([]uint32, 64*stride)
	var maskBase [64]int
	for s := 1; s < 64; s++ {
		base := s * stride
		maskBase[s] = base
		var cur uint32
		for i := 1; i <= n; i++ {
			cur += uint32(parity[s][a[i]])
			maskPref[base+i] = cur
		}
	}

	var comb [51][8]int64
	comb[0][0] = 1
	for i := 1; i <= 50; i++ {
		comb[i][0] = 1
		for k := 1; k <= 7; k++ {
			comb[i][k] = comb[i-1][k]
			comb[i][k] += comb[i-1][k-1]
		}
	}

	var coeff [51][51][8]int32
	for d := 0; d <= 50; d++ {
		for c := 0; c <= d; c++ {
			p := d - c
			for k := 0; k <= 7; k++ {
				var v int64
				for t := 0; t <= k; t++ {
					if t <= c && k-t <= p {
						term := comb[c][t] * comb[p][k-t]
						if t&1 == 1 {
							v -= term
						} else {
							v += term
						}
					}
				}
				coeff[d][c][k] = int32(v)
			}
		}
	}

	out := make([]byte, 0, q*20)

	for ; q > 0; q-- {
		l := fs.NextInt()
		r := fs.NextInt()
		left := l - 1
		length := r - l + 1

		cnt0 := int(valPref[valBase[0]+r] - valPref[valBase[0]+left])
		if cnt0 > 0 {
			out = strconv.AppendInt(out, int64(length-1), 10)
			out = append(out, ' ')
			out = strconv.AppendInt(out, int64(cnt0)%MOD, 10)
			out = append(out, '\n')
			continue
		}

		var pairWays int64
		dup := false
		for v := 1; v <= 50; v++ {
			c := int64(valPref[valBase[v]+r] - valPref[valBase[v]+left])
			if c >= 2 {
				dup = true
				pairWays += c * (c - 1) / 2
			}
		}
		if dup {
			out = strconv.AppendInt(out, int64(length-2), 10)
			out = append(out, ' ')
			out = strconv.AppendInt(out, pairWays%MOD, 10)
			out = append(out, '\n')
			continue
		}

		if length < 3 {
			out = append(out, '-', '1', '\n')
			continue
		}

		d := length
		var sum3, sum4, sum5, sum6, sum7 int64
		sum3 = int64(coeff[d][0][3])
		sum4 = int64(coeff[d][0][4])
		sum5 = int64(coeff[d][0][5])
		sum6 = int64(coeff[d][0][6])
		sum7 = int64(coeff[d][0][7])

		for s := 1; s < 64; s++ {
			c := int(maskPref[maskBase[s]+r] - maskPref[maskBase[s]+left])
			sum3 += int64(coeff[d][c][3])
			sum4 += int64(coeff[d][c][4])
			sum5 += int64(coeff[d][c][5])
			sum6 += int64(coeff[d][c][6])
			sum7 += int64(coeff[d][c][7])
		}

		c3 := sum3 / 64
		if c3 > 0 {
			out = strconv.AppendInt(out, int64(length-3), 10)
			out = append(out, ' ')
			out = strconv.AppendInt(out, c3%MOD, 10)
			out = append(out, '\n')
			continue
		}
		c4 := sum4 / 64
		if c4 > 0 {
			out = strconv.AppendInt(out, int64(length-4), 10)
			out = append(out, ' ')
			out = strconv.AppendInt(out, c4%MOD, 10)
			out = append(out, '\n')
			continue
		}
		c5 := sum5 / 64
		if c5 > 0 {
			out = strconv.AppendInt(out, int64(length-5), 10)
			out = append(out, ' ')
			out = strconv.AppendInt(out, c5%MOD, 10)
			out = append(out, '\n')
			continue
		}
		c6 := sum6 / 64
		if c6 > 0 {
			out = strconv.AppendInt(out, int64(length-6), 10)
			out = append(out, ' ')
			out = strconv.AppendInt(out, c6%MOD, 10)
			out = append(out, '\n')
			continue
		}
		c7 := sum7 / 64
		if c7 > 0 {
			out = strconv.AppendInt(out, int64(length-7), 10)
			out = append(out, ' ')
			out = strconv.AppendInt(out, c7%MOD, 10)
			out = append(out, '\n')
			continue
		}

		out = append(out, '-', '1', '\n')
	}

	os.Stdout.Write(out)
}