Problem Statement

Cloud Network Bandwidth Pricing Problem Description Background: A cloud provider maintains an unbounded set of data centers spread across the globe, each labeled with a distinct positive integer beginning at 1. Direct, two-way data links exist between: Data center i and data center 2i . Data center i and data center 2i + 1 . Any pair of data centers has exactly one shortest path connecting them. At the start, moving data between any two centers costs nothing. Over time, though, the provider adjusts bandwidth pricing on specific links as the network evolves. Updates arrive as one of two event types: 1. Fee Update: The provider raises the bandwidth fee by x units on every link lying along the shortest path connecting data centers a and b . 2. Data Transfer: A customer wants to move data from data center a to data center b , always via the shortest path. Work out the total cost this transfer incurs. Input: The first line contains an integer q (1 ≤ q ≤ 1,000), representing the number