描述

Alice在和Bob玩游戏。

在二人面前有一个不透明的盒子,里面装有n种球,球按种类编号1~n,第i种球有a_i个,他们每次从盒子里拿出一个球不放回,通过猜球的类型的成功次数决定胜负。

Bob觉得这个游戏太无聊了,于是他想出了一个奇怪的游戏玩法:每次从盒子里拿出一个球,如果拿出的球中第k种球(判定球)的数量达到了m个或者盒子里没有剩下球,那么游戏结束,否则重复游戏,最终胜负由摸到的第k'种球(计分球)的数量决定。一个人指定判定球、计分球的种类和判定球的数量上限,另一个人摸球,所以这个游戏玩两次,一次Alice摸球,一次Bob摸球。

Alice觉得这个游戏很新奇,他想知道一些情况下他能摸到的指定球的数量的数学期望,于是他找到了你,你非常轻松地接受了这个挑战。

(数学期望可以被认为是各种可能的得分按照其各自概率的加权平均数)

输入格式

第一行有两个正整数n和q,分别表示球的种类数和询问的次数。

第二行有n个空格隔开的正整数,第i个数a_i表示第i种球的个数是a_i

接下来q行,每行有三个空格隔开的整数k,m,k',表示判定球是第k种球,判定球的数量上限是m个,计分球是第k'种球。

输出格式

共q行,每行输出一个数,表示对应询问中计分球数量的数学期望,如果期望值不能化成整数,输出一个最简分数,否则输出整数。

样例输入

2 1
3 3
2 1 1

样例输出

3/4

数据范围与约定

  • 对于30%的数据:m=1
  • 对于60%的数据:1\le m\le10,1\le q\le 10^4
  • 对于100%的数据:1\le n,q\le10^5,1\le a_i,m\le10^9,1\le k,k'\le n

样例解释

游戏在摸到第2种球时结束,第1种球的数量的数学期望为\sum_{i=0}^{3}i*\frac{A_{3}^{i}*A_{3}^{1}}{A_{6}^{i+1}}=\frac{3}{4}

(A_n^m表示n个人中选m个人排成一队依次跪saffah的方案数,A_{n}^{m}=\frac{n!}{(n-m)!})

来源

签到题