本题没有可用的提交语言。

希尔伯特曲线与水平线段交点计数

问题描述

大卫·希尔伯特证明了一种反直觉的空间填充曲线存在。希尔伯特曲线的构造基于一系列曲线H₁, H₂, H₃...，每条曲线由水平和垂直线段组成，位于单位正方形[0,1]×[0,1]内。给定曲线Hₙ和一条水平线段，要求计算该线段与Hₙ曲线的垂直段交点数量。

输入格式

• 多组测试数据，每组格式为：
  n x₁ x₂ y
  表示Hₙ曲线和从(x₁/2ⁿ, y/2ⁿ)到(x₂/2ⁿ, y/2ⁿ)的水平线段
• 约束条件：
  • 0 < n < 31
  • x₁ < x₂
  • x₁, x₂, y ∈ [0, 2ⁿ]
• 输入以单独一行0结束

输出格式

每组数据输出一个整数：水平线段与Hₙ曲线的垂直段交点总数

示例

输入

3 2 7 7
4 0 16 1
30 1 1073741823 1

输出

3
16
1073741822