Alice 和 Marisa 都住在一个巨大的由 $N$ 个路口与 $M$ 条单向小道构成的森林中。Marisa 非常喜欢到 Alice 家里去玩，但是 Alice 并不喜欢这位鲁莽的来客。Alice 非常擅长观察， 因此每当她发现 Marisa 走了一条与之前完全相同的路径来到她家时，她就会装作不在家， Marisa 就只好败兴而归。Marisa 发现了这个秘密，因此她决定每次走不同的路径到 Alice 家。
Marisa 体力有限，她不想走超过 $K$ 条边到达 Alice 家，并且，每当她走 $t$（$t \leq K$）条边到达 Alice 家时，她需要付出 $t^2$ 的体力。Marisa 想知道，在 Alice 无论如何都不想接见她之前（即 Marisa 无法走一条长度不超过 $K$ 的与之前不同的路径），她会消耗多少体力。
现在 Marisa 拿到了一张森林的地图，但因为 Marisa 非常笨，她并不知道自己的家和 Alice 的家在哪一个路口，因此她会询问你 $Q$ 次，每次询问假如 Marisa 的家的位置在 $S$ 而 Alice 的家的位置在 $T$ 时的答案。
一条路径 $A$ 的定义是指一个长度为 $P$（$P$ 可以为任意正整数或零）的边的序列 $A_{m_0},A_{m_1},A_{m_2},\ldots,A_{m_{P-1}}$，其中对于任意 $1 \leq i < P$，有 $A_{m_{i-1}}$ 的结束节点是 $A_{m_i}$ 的起始节点。
两条路径 $A$ 和 $B$ 完全相同是指两条路径的长度均为 $T$ 并且对任意 $0 \leq i<P$，有 $A_{m_i}=B_{m_i}$。
LibreOJ