What is an appropriate data structure for this multiple-range problem?

I have a table of integers that looks like this:

|  Scalar | Range a | Range b |
|-----------------------------|
|    2    |   3-6   |   4-5   |
|    3    |   4-5   |   9-10  |
|    2    |   1-2   |   6-8   |

I want to be able to lookup a triple of integers and get the corresponding row index. For example: lookup(2,4,3) should return the row index of row 0. In the same way, lookup(3,6,8) should return nothing as it does not fit into any row.

Currently, my implementation relies in hashing the scalar column with an unordered_map, and then iterating through each bin in linear time to check the candidate triple against each range entry. The problem is, if there are many rows for the same scalar value the solution is too slow. Hence I need to find a way to speed up the lookup.

Efficiency is important as the table can contain thousands of rows with up to two hundred different ranges for the same scalar value.

Additionally: all entries and queries are integers and the values are never modified after creation. I also want to avoid using the boost libraries.