题目内容

工厂生产了 $n$ 种标准规格的正方形垫片，第 $i$ 种垫片的边长（同时也是厚度）记为 $a_i$。序列 $a$ 定义如下：$a_1=1,\, a_2=2$，且对于 $i>2$ 有 $a_i = a_{i-1} + a_{i-2}$。 现有 $m$ 个包装盒，第 $j$ 个盒子的底面为矩形，宽度为 $X_j$，长度为 $Y_j$，高度为 $Z_j$。 一个非空垫片子集 $S \subseteq \{1,2,\dots,n\}$ 能够放入第 $j$ 个盒子，当且仅当它同时满足以下两个条件：

• 子集中最大垫片边长不超过盒子底面的短边：$\max_{i \in S} a_i \le \min(X_j, Y_j)$；
• 子集中所有垫片的总厚度（边长之和）不超过盒子的高度：$\sum_{i \in S} a_i \le Z_j$。 对于每个盒子，请计算可以放入该盒子的非空垫片子集的数目。

数据范围：垫片种类数 $n$ 满足 $2 \le n \le 25$，盒子数量 $m$ 满足 $1 \le m \le 2 imes 10^5$。所有盒子的宽、长、高均为整数且不超过 $10^4$。一个测试文件中所有 $m$ 的总和不超过 $2 imes 10^5$。